{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Redundant Connection II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #union-find #graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #并查集 #图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findRedundantDirectedConnection"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #冗余连接 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在本问题中，有根树指满足以下条件的 <strong>有向</strong> 图。该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。</p>\n",
    "\n",
    "<p>输入一个有向图，该图由一个有着 <code>n</code> 个节点（节点值不重复，从 <code>1</code> 到 <code>n</code>）的树及一条附加的有向边构成。附加的边包含在 <code>1</code> 到 <code>n</code> 中的两个不同顶点间，这条附加的边不属于树中已存在的边。</p>\n",
    "\n",
    "<p>结果图是一个以边组成的二维数组 <code>edges</code> 。 每个元素是一对 <code>[u<sub>i</sub>, v<sub>i</sub>]</code>，用以表示 <strong>有向 </strong>图中连接顶点 <code>u<sub>i</sub></code> 和顶点 <code>v<sub>i</sub></code> 的边，其中 <code>u<sub>i</sub></code> 是 <code>v<sub>i</sub></code> 的一个父节点。</p>\n",
    "\n",
    "<p>返回一条能删除的边，使得剩下的图是有 <code>n</code> 个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/12/20/graph1.jpg\" style=\"width: 222px; height: 222px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>edges = [[1,2],[1,3],[2,3]]\n",
    "<strong>输出：</strong>[2,3]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/12/20/graph2.jpg\" style=\"width: 222px; height: 382px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>edges = [[1,2],[2,3],[3,4],[4,1],[1,5]]\n",
    "<strong>输出：</strong>[4,1]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == edges.length</code></li>\n",
    "\t<li><code>3 <= n <= 1000</code></li>\n",
    "\t<li><code>edges[i].length == 2</code></li>\n",
    "\t<li><code>1 <= u<sub>i</sub>, v<sub>i</sub> <= n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [redundant-connection-ii](https://leetcode.cn/problems/redundant-connection-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [redundant-connection-ii](https://leetcode.cn/problems/redundant-connection-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2],[1,3],[2,3]]', '[[1,2],[2,3],[3,4],[4,1],[1,5]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges):\n",
    "        n = len(edges)\n",
    "        parent = list(range(n + 1))\n",
    "\n",
    "        def findroot(node1):\n",
    "            while True:\n",
    "                t = parent[node1]\n",
    "                if t == node1:\n",
    "                    return t\n",
    "                node1 = t\n",
    "\n",
    "        conflictEdge = []\n",
    "        cycle = []\n",
    "\n",
    "        for i, (node1, node2) in enumerate(edges): # 有向边，从 node1 到 node2\n",
    "            if parent[node2] != node2:  # 不允许两个父节点\n",
    "                conflictEdge = (node1, node2)\n",
    "            elif findroot(node1) == findroot(node2):\n",
    "                cycle = (node1, node2)  # 产生环（根相同）\n",
    "            else:\n",
    "                parent[node2] = node1 # node2 的上一级是 node1\n",
    "\n",
    "        if not conflictEdge:  # 没有双父，就是环的边\n",
    "            return cycle\n",
    "\n",
    "        if cycle: # 只要有环，就是另一条边\n",
    "            return [parent[conflictEdge[1]], conflictEdge[1]]\n",
    "        # 没环，就是这条边\n",
    "        return conflictEdge"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        from queue import PriorityQueue\n",
    "\n",
    "        def findRoot(x):\n",
    "            p = parent.get(x, x)\n",
    "            if p != x:\n",
    "                parent[x] = findRoot(p)\n",
    "            \n",
    "            return parent.get(x, x)\n",
    "        \n",
    "        def union(x, y):\n",
    "            px, py = findRoot(x), findRoot(y)\n",
    "            if px != py:\n",
    "                parent[py] = px\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        parent = {}\n",
    "        n = len(edges)\n",
    "        graph = {i + 1: [] for i in range(n)}\n",
    "        ingraph = {i + 1: [] for i in range(n)}\n",
    "        edgeSet = set()\n",
    "        result = None\n",
    "        for i in range(n):\n",
    "            u, v = edges[i]\n",
    "            if (v, u) in edgeSet:\n",
    "                result = [u, v]\n",
    "            edgeSet.add((u, v))\n",
    "            graph[u].append((v, i))\n",
    "            ingraph[v].append((u, i))\n",
    "        \n",
    "        start = None\n",
    "        for node in graph:\n",
    "            if len(ingraph[node]) == 0:\n",
    "                start = node\n",
    "\n",
    "        if result is not None:\n",
    "            u, v = result\n",
    "            # print(u, v, start)\n",
    "            if len(ingraph[v]) == 1 and v != start and start is not None:\n",
    "                return [v, u]\n",
    "            else:\n",
    "                return [u, v]\n",
    "        \n",
    "        if start is None:\n",
    "            for u, v in edges:\n",
    "                if not union(u, v):\n",
    "                    return [u, v]\n",
    "        else:\n",
    "            q = PriorityQueue()\n",
    "            q.put((0, start, None))\n",
    "            result = None\n",
    "            while not q.empty():\n",
    "                _, u, prev = q.get()\n",
    "                if not union(prev, u):\n",
    "                    result = [prev, u]\n",
    "                else:\n",
    "                    for v, index in graph[u]:\n",
    "                        q.put((index, v, u))\n",
    "\n",
    "            curIndex = -1\n",
    "            for u, index in ingraph[result[1]]:\n",
    "                if index > curIndex:\n",
    "                    if (u == start and len(graph[u]) > 1) or u != start:\n",
    "                        result = [u, result[1]]\n",
    "                        curIndex = index\n",
    "                        \n",
    "            \n",
    "            return result\n",
    "            # return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n):\n",
    "        self.fa = [i for i in range(n)]\n",
    "    \n",
    "    def find(self, x):\n",
    "        return x if self.fa[x] == x else self.find(self.fa[x])\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        fx, fy = self.find(x), self.find(y)\n",
    "        if fx == fy: return 0\n",
    "        self.fa[y] = x\n",
    "        return 1\n",
    "\n",
    "    \n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        def toTreeCutEdge(edge):\n",
    "            uf = UF(n + 1)\n",
    "            for a, b in edges:\n",
    "                if [a, b] == edge: continue\n",
    "                # 去掉这条边以后依然不是树，说明答案不是这条边\n",
    "                if uf.union(a, b) == 0: return False\n",
    "            return True\n",
    "    \n",
    "        n = len(edges)\n",
    "        indegree = [0] * (n + 1)\n",
    "        for _, e in edges: indegree[e] += 1\n",
    "        \n",
    "        if 2 in indegree:\n",
    "            target = indegree.index(2)\n",
    "            for i in range(n - 1, -1, -1):\n",
    "                # 入度存在 2， 则要删去入度为 2 的点连接的一条边\n",
    "                if edges[i][1] == target and toTreeCutEdge(edges[i]):\n",
    "                    return edges[i]\n",
    "            \n",
    "        \n",
    "        # 入度不存在 2 ，图中存在有向环，找到最后出现的有向环的边即可\n",
    "        uf = UF(n + 1)\n",
    "        # for a, b in edges: uf.union(a, b)  # 这里注意不能一开始就全合并，不然很多边的祖先都是同一个\n",
    "        for a, b in edges:\n",
    "            if uf.find(a) == uf.find(b):  # 先判断，再合并\n",
    "                return [a, b]\n",
    "            uf.union(a, b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n):\n",
    "        self.fa = [i for i in range(n)]\n",
    "    \n",
    "    def find(self, x):\n",
    "        return x if self.fa[x] == x else self.find(self.fa[x])\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        fx, fy = self.find(x), self.find(y)\n",
    "        if fx == fy: return 0\n",
    "        self.fa[y] = x\n",
    "        return 1\n",
    "\n",
    "    \n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        def toTreeCutEdge(edge):\n",
    "            uf = UF(n + 1)\n",
    "            for a, b in edges:\n",
    "                if [a, b] == edge: continue\n",
    "                # 去掉这条边以后依然不是树，说明答案不是这条边\n",
    "                if uf.union(a, b) == 0: return False\n",
    "            return True\n",
    "    \n",
    "        n = len(edges)\n",
    "        indegree = [0] * (n + 1)\n",
    "        for _, e in edges: indegree[e] += 1\n",
    "        # print(indegree)\n",
    "        if 2 in indegree:\n",
    "            target = indegree.index(2)\n",
    "            for i in range(n - 1, -1, -1):\n",
    "                # 入度存在 2， 则要删去入度为 2 的点连接的一条边\n",
    "                if edges[i][1] == target and toTreeCutEdge(edges[i]):\n",
    "                    # print(1)\n",
    "                    return edges[i]\n",
    "            \n",
    "        \n",
    "        # 入度不存在 2 ，图中存在有向环，找到最后出现的有向环的边即可\n",
    "        uf = UF(n + 1)\n",
    "        # for a, b in edges: uf.union(a, b)  # 这里注意不能一开始就全合并，不然很多边的祖先都是同一个\n",
    "        for a, b in edges:\n",
    "            if uf.find(a) == uf.find(b):  # 先判断，再合并\n",
    "                return [a, b]\n",
    "            uf.union(a, b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        father = [ i for i in range(1005)]\n",
    "        def find(u):\n",
    "            if u == father[u]:\n",
    "                return u\n",
    "            else:\n",
    "                return find(father[u])\n",
    "\n",
    "        def join(u,v):\n",
    "            u = find(u)\n",
    "            v = find(v)\n",
    "            if u == v:\n",
    "                return\n",
    "            father[v] = u\n",
    "            return\n",
    "        \n",
    "        def same(u,v):\n",
    "            u = find(u)\n",
    "            v = find(v)\n",
    "            return u == v\n",
    "        \n",
    "        def checktree(f,edges,specific):\n",
    "            for edge in edges:\n",
    "                if edge == specific:\n",
    "                    continue\n",
    "                if same(edge[0],edge[1]):\n",
    "                    return False\n",
    "                else:\n",
    "                    join(edge[0],edge[1])\n",
    "            return True\n",
    "\n",
    "\n",
    "        indegree = [0] * 1005\n",
    "        ru = -1\n",
    "        for i in range(len(edges)):\n",
    "            indegree[edges[i][1]] += 1\n",
    "            if indegree[edges[i][1]] == 2:\n",
    "                ru = edges[i][1]\n",
    "                break\n",
    "        forcheck = []\n",
    "        if ru != -1:\n",
    "            for i in range(len(edges)):\n",
    "                if edges[i][1] == ru:\n",
    "                    forcheck.append(edges[i][0])\n",
    "            if checktree(father, edges, [forcheck[1],ru]):\n",
    "                return [forcheck[1],ru]\n",
    "            else:\n",
    "                return [forcheck[0],ru]\n",
    "        else:\n",
    "            for edge in edges:\n",
    "                if same(edge[0],edge[1]):\n",
    "                    return edge\n",
    "                else:\n",
    "                    join(edge[0],edge[1])            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    from collections import defaultdict\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        parent = [i for i in range(len(edges)+1)]\n",
    "        def find(p):\n",
    "            if p != parent[p]:\n",
    "                return find(parent[p])\n",
    "            return p\n",
    "        cycle, conflict = -1, -1\n",
    "        for idx, (u, v) in enumerate(edges):\n",
    "            if v != parent[v]:\n",
    "                conflict = idx\n",
    "            else:\n",
    "                if v == find(u):\n",
    "                    cycle = idx\n",
    "                else:\n",
    "                    parent[v] = u\n",
    "        if conflict == -1:\n",
    "            return edges[cycle]\n",
    "        elif cycle == -1:\n",
    "            return edges[conflict]\n",
    "        else:\n",
    "            return [parent[edges[conflict][1]], edges[conflict][1]]\n",
    "\n",
    "        # n = 1\n",
    "        # in_degree = collections.defaultdict(int)\n",
    "        # out_degree = collections.defaultdict(int)\n",
    "        # for i in range(len(edges)):\n",
    "        #     u,v = edges[i]\n",
    "        #     n = max(n,u,v)\n",
    "        #     in_degree[v] += 1\n",
    "        #     out_degree[u] += 1\n",
    "        #     edges[i] = (u,v)\n",
    "        # conflict = []\n",
    "        # for u,v in edges:\n",
    "        #     if in_degree[v] == 2: conflict.append((u,v))\n",
    "\n",
    "        # def checkcicle(pattern,n):\n",
    "        #     dic = collections.defaultdict(list)\n",
    "        #     for ele in pattern:\n",
    "        #         dic[ele[0]].append(ele[1])\n",
    "        #     visited = [False]*(n+1)\n",
    "        #     def dfs(idx):\n",
    "        #         if visited[idx]: return True\n",
    "        #         visited[idx] = True\n",
    "        #         for nextidx in dic[idx]:\n",
    "        #             if dfs(nextidx): return True\n",
    "        #         visited[idx] = False\n",
    "        #         return False\n",
    "        #     for i in range(1,n+1):\n",
    "        #         if dfs(i): return True\n",
    "        #     return False\n",
    "\n",
    "        # if conflict == []:\n",
    "        #     for edge in reversed(edges):\n",
    "        #         newedges = set(edges)\n",
    "        #         newedges.remove(edge)\n",
    "        #         if not checkcicle(newedges,n): return list(edge)\n",
    "        # newedges = set(edges)\n",
    "        # newedges.remove(conflict[1])\n",
    "        # if not checkcicle(newedges,n): return list(conflict[1])\n",
    "        # else: return list(conflict[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        def find_parent(node1,node2):\n",
    "            print(node1)\n",
    "            if node1 == node2:\n",
    "                return True\n",
    "            if parent[node1] != node1:\n",
    "                return find_parent(parent[node1],node2)\n",
    "            return False\n",
    "        parent = list(range(len(edges)+1))\n",
    "        temp = collections.defaultdict(list)\n",
    "        max_ = 0\n",
    "        flag = 0\n",
    "        for i in edges:\n",
    "            if i[1] in temp.keys():\n",
    "                flag = i[1]\n",
    "            temp[i[1]].append(i[0])\n",
    "            parent[i[1]] = i[0]\n",
    "            # root  \n",
    "        if flag != 0:\n",
    "            #root is not in the circle\n",
    "            for i in temp[flag][::-1]:\n",
    "                if find_parent(i,flag):\n",
    "                    #find circle\n",
    "                    return [i,flag]\n",
    "            return [temp[flag][-1],flag]\n",
    "            out = list(temp.keys())[-1]\n",
    "            return [temp[out],out]\n",
    "        else:\n",
    "            #root is in the circle\n",
    "            parent = list(range(len(edges)+1))\n",
    "            max_ = 0\n",
    "            for i in edges:\n",
    "                if find_parent(i[0],i[1]):\n",
    "                    #find circle\n",
    "                    return i\n",
    "                parent[i[1]] = i[0]\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        parent = list(range(len(edges) + 1))\n",
    "        conflicts = list(range(len(edges) + 1))\n",
    "\n",
    "        def find(x):\n",
    "            if parent[x] != x:\n",
    "                parent[x] = find(parent[x])\n",
    "            \n",
    "            return parent[x]\n",
    "\n",
    "        def union(x, y):\n",
    "            a = find(x)\n",
    "            b = find(y)\n",
    "            parent[a] = b\n",
    "\n",
    "\n",
    "        # 有环无冲突 [[1,2],[2,3],[3,1]]，每个节点的出入度都是1, 随便断开一条边就行, 也就是edges[-1]\n",
    "        # 有环有冲突 [[1,2],[2,3],[3,1],[4,2]]，说明有一个节点的入度是2, 且其中一条边是环路边, 一条边是冲突边, 断开环路边.\n",
    "        # 无环有冲突 [[1,2],[1,3],[2,3]]，明有一个节点的入度是2, 断开冲突边即可\n",
    "        conflict = -1\n",
    "        cycle = -1\n",
    "        for i, (a,b) in enumerate(edges):\n",
    "            if conflicts[b] != b:\n",
    "                conflict = i\n",
    "            else:\n",
    "                conflicts[b] = a\n",
    "                if find(a) == find(b):\n",
    "                    cycle = i\n",
    "                else:\n",
    "                    union(a, b)\n",
    "        \n",
    "        if conflict < 0:\n",
    "            return [edges[cycle][0], edges[cycle][1]]\n",
    "        \n",
    "        conf_edg = edges[conflict]\n",
    "        if cycle > 0:\n",
    "            return [conflicts[conf_edg[1]], conf_edg[1]]\n",
    "\n",
    "        return [conf_edg[0], conf_edg[1]]\n",
    "\n",
    "    \n",
    "\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        d = {}\n",
    "        count = [0]*(len(edges)+1)\n",
    "        for i in edges:\n",
    "            if i[0] not in d:\n",
    "                d[i[0]] = []\n",
    "            d[i[0]].append(i[1])\n",
    "            count[i[1]] += 1\n",
    "        def dfs(now,d):\n",
    "            a = 1\n",
    "            if now not in d:\n",
    "                return a\n",
    "            for i in d[now]:\n",
    "                a += dfs(i,d)\n",
    "            return a\n",
    "        for i in edges[::-1]:\n",
    "            d[i[0]].remove(i[1])\n",
    "            count[i[1]] -= 1\n",
    "            start = -1\n",
    "            flag = 0\n",
    "            for j in range(1,len(count)):\n",
    "                if start == -1 and count[j] == 0:\n",
    "                    start = j\n",
    "                    flag = 1\n",
    "                else:\n",
    "                    if count[j] == 0:\n",
    "                        flag = 0\n",
    "            #print(start,d,dfs(start,d))\n",
    "            if flag and dfs(start,d) == len(edges):\n",
    "                return i\n",
    "            count[i[1]] += 1\n",
    "            d[i[0]].append(i[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.n = 1010\n",
    "        self.father = [i for i in range(self.n)]\n",
    "\n",
    "    def find(self, u):\n",
    "        if u == self.father[u]:\n",
    "            return u\n",
    "        self.father[u] = self.find(self.father[u])\n",
    "        return self.father[u]\n",
    "\n",
    "    def join(self, u, v):\n",
    "        u = self.find(u)\n",
    "        v = self.find(v)\n",
    "        if u == v: return\n",
    "        self.father[v] = u\n",
    "\n",
    "    def isSame(self, u, v):\n",
    "        u = self.find(u)\n",
    "        v = self.find(v)\n",
    "        return u == v\n",
    "\n",
    "    def init_father(self):\n",
    "        self.father = [i for i in range(self.n)]\n",
    "\n",
    "    def isTreeAfterRemoveEdge(self, edges, deleteEdge):\n",
    "        self.init_father()\n",
    "        for i in range(len(edges)):\n",
    "            if i == deleteEdge: continue\n",
    "            if self.isSame(edges[i][0], edges[i][1]): # 有向环\n",
    "                return False\n",
    "            self.join(edges[i][0], edges[i][1])\n",
    "\n",
    "        return True\n",
    "\n",
    "    def getRemoveEdge(self, edges):\n",
    "        self.init_father()\n",
    "        for i in range(len(edges)):\n",
    "            if self.isSame(edges[i][0], edges[i][1]):\n",
    "                return edges[i]\n",
    "            self.join(edges[i][0], edges[i][1])\n",
    "        return []\n",
    "\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        inDegree = [0 for i in range(self.n)]\n",
    "\n",
    "        for i in range(len(edges)):\n",
    "            inDegree[edges[i][1]] += 1\n",
    "\n",
    "        twoDegree = []\n",
    "        for i in range(len(edges)-1, -1, -1):\n",
    "            if inDegree[edges[i][1]] == 2:\n",
    "                twoDegree.append(i)\n",
    "\n",
    "        if len(twoDegree) > 0:\n",
    "            if self.isTreeAfterRemoveEdge(edges, twoDegree[0]):\n",
    "                return edges[twoDegree[0]]\n",
    "            return edges[twoDegree[1]]\n",
    "\n",
    "        return self.getRemoveEdge(edges)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        parent = list(range(n + 1))\n",
    "\n",
    "        def findroot(node1):\n",
    "            while True:\n",
    "                t = parent[node1]\n",
    "                if t == node1:\n",
    "                    return t\n",
    "                node1 = t\n",
    "\n",
    "        conflictEdge = []\n",
    "        cycle = []\n",
    "\n",
    "        for i, (node1, node2) in enumerate(edges): # 有向边，从 node1 到 node2\n",
    "            if parent[node2] != node2:  # 不允许两个父节点\n",
    "                conflictEdge = (node1, node2)\n",
    "            elif findroot(node1) == findroot(node2):\n",
    "                cycle = (node1, node2)  # 产生环（根相同）\n",
    "            else:\n",
    "                parent[node2] = node1 # node2 的上一级是 node1\n",
    "\n",
    "        if not conflictEdge:  # 没有双父，就是环的边\n",
    "            return cycle\n",
    "\n",
    "        if cycle: # 只要有环，就是另一条边\n",
    "            return [parent[conflictEdge[1]], conflictEdge[1]]\n",
    "        # 没环，就是这条边\n",
    "        return conflictEdge"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        parent = list(range(n + 1))\n",
    "\n",
    "        def findroot(node1):\n",
    "            while True:\n",
    "                t = parent[node1]\n",
    "                if t == node1:\n",
    "                    return t\n",
    "                node1 = t\n",
    "\n",
    "        conflictEdge = []\n",
    "        cycle = []\n",
    "\n",
    "        for i, (node1, node2) in enumerate(edges): # 有向边，从 node1 到 node2\n",
    "            if parent[node2] != node2:  # 不允许两个父节点\n",
    "                conflictEdge = (node1, node2)\n",
    "            elif findroot(node1) == findroot(node2):\n",
    "                cycle = (node1, node2)  # 产生环（根相同）\n",
    "            else:\n",
    "                parent[node2] = node1 # node2 的上一级是 node1\n",
    "\n",
    "        if not conflictEdge:  # 没有双父，就是环的边\n",
    "            return cycle\n",
    "\n",
    "        if cycle: # 只要有环，就是另一条边\n",
    "            return [parent[conflictEdge[1]], conflictEdge[1]]\n",
    "        # 没环，就是这条边\n",
    "        return conflictEdge"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.ancestor = list(range(n))\n",
    "    \n",
    "    def union(self, index1: int, index2: int):\n",
    "        self.ancestor[self.find(index1)] = self.find(index2)\n",
    "    \n",
    "    def find(self, index: int) -> int:\n",
    "        if self.ancestor[index] != index:\n",
    "            self.ancestor[index] = self.find(self.ancestor[index])\n",
    "        return self.ancestor[index]\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        uf = UnionFind(n + 1)\n",
    "        parent = list(range(n + 1))\n",
    "        conflict = -1\n",
    "        cycle = -1\n",
    "        for i, (node1, node2) in enumerate(edges):\n",
    "            if parent[node2] != node2:\n",
    "                conflict = i\n",
    "            else:\n",
    "                parent[node2] = node1\n",
    "                if uf.find(node1) == uf.find(node2):\n",
    "                    cycle = i\n",
    "                else:\n",
    "                    uf.union(node1, node2)\n",
    "\n",
    "        if conflict < 0:\n",
    "            return [edges[cycle][0], edges[cycle][1]]\n",
    "        else:\n",
    "            conflictEdge = edges[conflict]\n",
    "            if cycle >= 0:\n",
    "                return [parent[conflictEdge[1]], conflictEdge[1]]\n",
    "            else:\n",
    "                return [conflictEdge[0], conflictEdge[1]]\n",
    "\n",
    "\n",
    "                \n",
    "        \n",
    "\n",
    "                \n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        #初始化祖先为自身，即无祖先\n",
    "        self.ancestor = list(range(n))\n",
    "    # 将index1所在的集合加入到index2的集合中\n",
    "    def union(self, index1: int, index2: int):\n",
    "        #index1的祖先的祖先设置为index2的祖先\n",
    "        self.ancestor[self.find(index1)] = self.find(index2)\n",
    "    # 找到祖先\n",
    "    def find(self, index: int) -> int:\n",
    "        if self.ancestor[index] != index:\n",
    "            self.ancestor[index] = self.find(self.ancestor[index])\n",
    "        return self.ancestor[index]\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        # 辅助数组parent以及并查集初始化\n",
    "        nodesCount = len(edges)\n",
    "        uf = UnionFind(nodesCount + 1)#现在所有结点都暂无祖先\n",
    "        parent = list(range(nodesCount + 1))#父节点也都是自己本身\n",
    "        # 冲突/环标签\n",
    "        conflict = -1\n",
    "        cycle = -1\n",
    "        # 开始遍历\n",
    "        for i, (node1, node2) in enumerate(edges):\n",
    "            if parent[node2] != node2:  # 产生冲突（有两个父节点）\n",
    "                conflict = i\n",
    "                continue\n",
    "            parent[node2] = node1\n",
    "            if uf.find(node1) == uf.find(node2):\n",
    "                cycle = i  # 产生环（祖先相同）\n",
    "            else:\n",
    "                uf.union(node1, node2)  # 合并，就是一点一点延长树\n",
    "        # 获取有问题的边\n",
    "        if conflict < 0:  # 没有冲突就是环的边\n",
    "            return [edges[cycle][0], edges[cycle][1]]\n",
    "        conflictEdge = edges[conflict]\n",
    "        if cycle >= 0:\n",
    "            return [parent[conflictEdge[1]], conflictEdge[1]]  # 环存在，并且冲突也存在，优先删除在环上的边\n",
    "        return [conflictEdge[0], conflictEdge[1]]  # 无环就是冲突边"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        parent = list(range(n + 1))\n",
    "\n",
    "        def findroot(node1):\n",
    "            while True:\n",
    "                t = parent[node1]\n",
    "                if t == node1:\n",
    "                    return t\n",
    "                node1 = t\n",
    "\n",
    "        conflictEdge = []\n",
    "        cycle = []\n",
    "\n",
    "        for i, (node1, node2) in enumerate(edges): # 有向边，从 node1 到 node2\n",
    "            if parent[node2] != node2:  # 不允许两个父节点\n",
    "                conflictEdge = (node1, node2)\n",
    "            elif findroot(node1) == findroot(node2):\n",
    "                cycle = (node1, node2)  # 产生环（根相同）\n",
    "            else:\n",
    "                parent[node2] = node1 # node2 的上一级是 node1\n",
    "\n",
    "        if not conflictEdge:  # 没有双父，就是环的边\n",
    "            return cycle\n",
    "\n",
    "        if cycle: # 只要有环，就是另一条边\n",
    "            return [parent[conflictEdge[1]], conflictEdge[1]]\n",
    "        # 没环，就是这条边\n",
    "        return conflictEdge"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        parent = list(range(n + 1))\n",
    "\n",
    "        def findroot(node1):\n",
    "            while True:\n",
    "                t = parent[node1]\n",
    "                if t == node1:\n",
    "                    return t\n",
    "                node1 = t\n",
    "\n",
    "        conflictEdge = []\n",
    "        cycle = []\n",
    "\n",
    "        for i, (node1, node2) in enumerate(edges): # 有向边，从 node1 到 node2\n",
    "            if parent[node2] != node2:  # 不允许两个父节点\n",
    "                conflictEdge = (node1, node2)\n",
    "            elif findroot(node1) == findroot(node2):\n",
    "                cycle = (node1, node2)  # 产生环（根相同）\n",
    "            else:\n",
    "                parent[node2] = node1 # node2 的上一级是 node1\n",
    "\n",
    "        if not conflictEdge:  # 没有双父，就是环的边\n",
    "            return cycle\n",
    "\n",
    "        if cycle: # 只要有环，就是另一条边\n",
    "            return [parent[conflictEdge[1]], conflictEdge[1]]\n",
    "        # 没环，就是这条边\n",
    "        return conflictEdge"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        parents = list(range(n+1))\n",
    "\n",
    "        def find_root(node):\n",
    "            while True:\n",
    "                t = parents[node]\n",
    "                if t == node:\n",
    "                    return t\n",
    "                node = t\n",
    "\n",
    "        conflictEdge = []\n",
    "        cycle = []\n",
    "        for node1, node2 in edges:\n",
    "            if parents[node2] != node2:\n",
    "                conflictEdge = [node1, node2]\n",
    "            elif find_root(node1) == find_root(node2):\n",
    "                cycle = [node1,node2]\n",
    "            else:\n",
    "                parents[node2] = node1\n",
    "\n",
    "        if not conflictEdge:\n",
    "            return cycle[0],cycle[1]\n",
    "        if cycle:\n",
    "            return parents[conflictEdge[1]],conflictEdge[1]\n",
    "\n",
    "        return  conflictEdge[0],conflictEdge[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        self.degree = {}\n",
    "        Num2Degree = []\n",
    "        for i in range(len(edges)):\n",
    "            self.degree[i] = []\n",
    "        for i in range(len(edges)):\n",
    "            self.degree[edges[i][1]-1].append(i)\n",
    "            if len(self.degree[edges[i][1]-1]) == 2:\n",
    "                Num2Degree = self.degree[edges[i][1]-1][:]\n",
    "        # print(Num2Degree)\n",
    "        if not Num2Degree:\n",
    "            return edges[self.getRemoveEdge(edges)]\n",
    "        else:\n",
    "\n",
    "            for i in range(len(Num2Degree)-1,-1,-1):\n",
    "                # print(\"Num2Degree[i] is\",Num2Degree[i])\n",
    "                if self.isTreeAfterRemoveEdge(edges, Num2Degree[i]):\n",
    "                    return edges[Num2Degree[i]]\n",
    "    \n",
    "\n",
    "    \n",
    "\n",
    "\n",
    "    def isTreeAfterRemoveEdge(self, edges, delete_i):\n",
    "        self.father = [i for i in range(len(edges))]\n",
    "        for i in range(len(edges)):\n",
    "            if i != delete_i:\n",
    "                u = self.find(edges[i][0]-1)\n",
    "                v = self.find(edges[i][1]-1)\n",
    "                if u != v:\n",
    "                    self.father[v] = u\n",
    "                else:\n",
    "                    return False\n",
    "        return True\n",
    "\n",
    "    def getRemoveEdge(self, edges):\n",
    "        for i in range(len(edges)-1, -1, -1):\n",
    "            if self.isTreeAfterRemoveEdge(edges,i):\n",
    "                return i\n",
    "        \n",
    "\n",
    "    def find(self, u):\n",
    "        if u == self.father[u]:\n",
    "            return u\n",
    "        else:\n",
    "            self.father[u] = self.find(self.father[u])\n",
    "            return self.father[u]\n",
    "    \n",
    "    def join(self, u, v):\n",
    "        u = self.find(u)\n",
    "        v = self.find(v)\n",
    "        if u != v:\n",
    "            self.father[v] = u\n",
    "        return\n",
    "\n",
    "    def isSame(self, u, v):\n",
    "        return self.find(u) == self.find(v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "            # 初始化\n",
    "            self.n = 1010\n",
    "            self.mapping = [i for i in range(self.n+1)]\n",
    "\n",
    "    def initFather(self):\n",
    "        self.mapping = [i for i in range(self.n + 1)]\n",
    "    \n",
    "    def find(self,node):\n",
    "        if self.mapping[node] == node:\n",
    "            return node\n",
    "        else:\n",
    "            self.mapping[node] = self.find(self.mapping[node])\n",
    "            return self.mapping[node]\n",
    "        \n",
    "    def isTreeAfterRemoveEdge(self,edges,delete_edge):\n",
    "        self.initFather()\n",
    "        for i in range(len(edges)):\n",
    "            if edges[i] == delete_edge:\n",
    "                continue\n",
    "            else:\n",
    "                root1 = self.find(edges[i][0])\n",
    "                root2 = self.find(edges[i][1])\n",
    "                # 删除这条边后\n",
    "                if root1 == root2:\n",
    "                    return False\n",
    "                self.mapping[root1] = root2\n",
    "\n",
    "        return True\n",
    "\n",
    "    def getRemoveEdge(self,edges):\n",
    "        self.initFather()\n",
    "        for i in edges:\n",
    "            if self.find(i[0]) == self.find(i[1]):\n",
    "                return i\n",
    "            else:\n",
    "                root1 = self.find(i[0]) \n",
    "                root2 = self.find(i[1])\n",
    "                self.mapping[root1] = root2\n",
    "        return \n",
    "\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "\n",
    "        # 计算节点的入度\n",
    "        rudu = {}\n",
    "        for i in range(len(edges)):\n",
    "            rudu[edges[i][1]] = rudu.get(edges[i][1],0) + 1\n",
    "        \n",
    "        # 入度为2的边\n",
    "        rudu_2 = []\n",
    "        for i in range(len(edges)-1,-1,-1):\n",
    "            if rudu[edges[i][1]] > 1:\n",
    "                rudu_2.append(edges[i])\n",
    "\n",
    "        # 删除入度大于2的节点的某条入边\n",
    "        if len(rudu_2) > 1:\n",
    "            if self.isTreeAfterRemoveEdge(edges,rudu_2[0]):\n",
    "                return rudu_2[0]\n",
    "            else:\n",
    "                return rudu_2[1]\n",
    "\n",
    "\n",
    "        # 成环了，删除环里的边\n",
    "        else:\n",
    "            return self.getRemoveEdge(edges)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def init_father(self, n):\n",
    "        self.father = [i for i in range(n+1)]\n",
    "    def find(self, u):\n",
    "        if u == self.father[u]:\n",
    "            return u\n",
    "        self.father[u] = self.find(self.father[u])\n",
    "        return self.father[u]\n",
    "    def isSame(self, u, v):\n",
    "        return self.find(u) == self.find(v)\n",
    "    def join(self, u, v):\n",
    "        u = self.find(u)\n",
    "        v = self.find(v)\n",
    "        if u == v: return \n",
    "        self.father[v] = u\n",
    "\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        ##并查集\n",
    "        \n",
    "        n = len(edges)\n",
    "        self.init_father(n)\n",
    "        graph = [[] for i in range(n+1)]\n",
    "        for p, q in edges:\n",
    "            graph[q].append(p)\n",
    "        for p,q in edges:\n",
    "            if len(graph[q]) == 1:\n",
    "                if self.isSame(p, q):\n",
    "                    return [p, q]\n",
    "                self.join(p, q)\n",
    "\n",
    "        for i in range(n+1):\n",
    "            if len(graph[i]) == 2:\n",
    "                for p in graph[i]:\n",
    "                    if self.isSame(p, i):\n",
    "                        return [p, i]\n",
    "                    self.join(p, i)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def __init__(self) -> None:\r\n",
    "        self.n = 1010 \r\n",
    "        self.father = [i for i in range(self.n)]\r\n",
    "\r\n",
    "    def find(self,u):\r\n",
    "        if u== self.father[u]:\r\n",
    "            return u \r\n",
    "        self.father[u] = self.find(self.father[u])\r\n",
    "        return self.father[u]\r\n",
    "    \r\n",
    "    def join(self,u,v):\r\n",
    "        u = self.find(u)\r\n",
    "        v = self.find(v)\r\n",
    "        if u==v:return \r\n",
    "        self.father[v]=u \r\n",
    "\r\n",
    "    def same(self,u,v):\r\n",
    "        u = self.find(u)\r\n",
    "        v = self.find(v)\r\n",
    "        return u==v \r\n",
    "    def init_father(self):\r\n",
    "        self.father = [i for i in range(self.n)]\r\n",
    "\r\n",
    "    def getRemoveEdge(self,edges):\r\n",
    "        self.init_father()\r\n",
    "        for i in range(len(edges)):\r\n",
    "            if self.same(edges[i][0],edges[i][1]):\r\n",
    "                return edges[i]\r\n",
    "            self.join(edges[i][0],edges[i][1])\r\n",
    "        return []\r\n",
    "    \r\n",
    "    def isTreeAfterRemoveEdge(self,edges,deleteEdge):\r\n",
    "        self.init_father()\r\n",
    "        for i in range(len(edges)):\r\n",
    "            if i ==deleteEdge:continue \r\n",
    "            if self.same(edges[i][0],edges[i][1]):\r\n",
    "                return False\r\n",
    "            self.join(edges[i][0],edges[i][1])\r\n",
    "        return True\r\n",
    "\r\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\r\n",
    "        inDegree = [0 for i in range(self.n)]\r\n",
    "        for i in range(len(edges)):\r\n",
    "            inDegree[edges[i][1]] +=1\r\n",
    "\r\n",
    "        twoDegree = []\r\n",
    "        for i in range(len(edges))[::-1]:\r\n",
    "            if inDegree[edges[i][1]]==2:\r\n",
    "                twoDegree.append(i)\r\n",
    "\r\n",
    "        if len(twoDegree)>0:\r\n",
    "            if (self.isTreeAfterRemoveEdge(edges,twoDegree[0])):\r\n",
    "                return edges[twoDegree[0]]\r\n",
    "            return edges[twoDegree[1]]\r\n",
    "        \r\n",
    "        return self.getRemoveEdge(edges)\r\n",
    "    \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        self.degree = {}\n",
    "        Num2Degree = []\n",
    "        for i in range(len(edges)):\n",
    "            self.degree[i] = []\n",
    "        for i in range(len(edges)):\n",
    "            self.degree[edges[i][1]-1].append(i)\n",
    "            if len(self.degree[edges[i][1]-1]) == 2:\n",
    "                Num2Degree = self.degree[edges[i][1]-1][:]\n",
    "        print(Num2Degree)\n",
    "        if not Num2Degree:\n",
    "            return edges[self.getRemoveEdge(edges)]\n",
    "        else:\n",
    "\n",
    "            for i in range(len(Num2Degree)-1,-1,-1):\n",
    "                # print(\"Num2Degree[i] is\",Num2Degree[i])\n",
    "                if self.isTreeAfterRemoveEdge(edges, Num2Degree[i]):\n",
    "                    return edges[Num2Degree[i]]\n",
    "    \n",
    "\n",
    "    \n",
    "\n",
    "\n",
    "    def isTreeAfterRemoveEdge(self, edges, delete_i):\n",
    "        self.father = [i for i in range(len(edges))]\n",
    "        for i in range(len(edges)):\n",
    "            if i != delete_i:\n",
    "                u = self.find(edges[i][0]-1)\n",
    "                v = self.find(edges[i][1]-1)\n",
    "                if u != v:\n",
    "                    self.father[v] = u\n",
    "                else:\n",
    "                    return False\n",
    "        return True\n",
    "\n",
    "    def getRemoveEdge(self, edges):\n",
    "        for i in range(len(edges)-1, -1, -1):\n",
    "            if self.isTreeAfterRemoveEdge(edges,i):\n",
    "                return i\n",
    "        \n",
    "\n",
    "    def find(self, u):\n",
    "        if u == self.father[u]:\n",
    "            return u\n",
    "        else:\n",
    "            self.father[u] = self.find(self.father[u])\n",
    "            return self.father[u]\n",
    "    \n",
    "    def join(self, u, v):\n",
    "        u = self.find(u)\n",
    "        v = self.find(v)\n",
    "        if u != v:\n",
    "            self.father[v] = u\n",
    "        return\n",
    "\n",
    "    def isSame(self, u, v):\n",
    "        return self.find(u) == self.find(v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        self.degree = {}\n",
    "        Num2Degree = []\n",
    "        for i in range(len(edges)):\n",
    "            self.degree[i] = []\n",
    "        for i in range(len(edges)):\n",
    "            self.degree[edges[i][1]-1].append(i)\n",
    "            if len(self.degree[edges[i][1]-1]) == 2:\n",
    "                Num2Degree = self.degree[edges[i][1]-1][:]\n",
    "        print(Num2Degree)\n",
    "        if not Num2Degree:\n",
    "            return edges[self.getRemoveEdge(edges)]\n",
    "        else:\n",
    "\n",
    "            for i in range(len(Num2Degree)-1,-1,-1):\n",
    "                print(\"Num2Degree[i] is\",Num2Degree[i])\n",
    "                if self.isTreeAfterRemoveEdge(edges, Num2Degree[i]):\n",
    "                    return edges[Num2Degree[i]]\n",
    "    \n",
    "\n",
    "    \n",
    "\n",
    "\n",
    "    def isTreeAfterRemoveEdge(self, edges, delete_i):\n",
    "        self.father = [i for i in range(len(edges))]\n",
    "        for i in range(len(edges)):\n",
    "            if i != delete_i:\n",
    "                u = self.find(edges[i][0]-1)\n",
    "                v = self.find(edges[i][1]-1)\n",
    "                if u != v:\n",
    "                    self.father[v] = u\n",
    "                else:\n",
    "                    return False\n",
    "        return True\n",
    "\n",
    "    def getRemoveEdge(self, edges):\n",
    "        for i in range(len(edges)-1, -1, -1):\n",
    "            if self.isTreeAfterRemoveEdge(edges,i):\n",
    "                return i\n",
    "        \n",
    "\n",
    "    def find(self, u):\n",
    "        if u == self.father[u]:\n",
    "            return u\n",
    "        else:\n",
    "            self.father[u] = self.find(self.father[u])\n",
    "            return self.father[u]\n",
    "    \n",
    "    def join(self, u, v):\n",
    "        u = self.find(u)\n",
    "        v = self.find(v)\n",
    "        if u != v:\n",
    "            self.father[v] = u\n",
    "        return\n",
    "\n",
    "    def isSame(self, u, v):\n",
    "        return self.find(u) == self.find(v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        parent = list(range(n + 1))\n",
    "\n",
    "        def findroot(node1):\n",
    "            while True:\n",
    "                t = parent[node1]\n",
    "                if t == node1:\n",
    "                    return t\n",
    "                node1 = t\n",
    "\n",
    "        conflictEdge = []\n",
    "        cycle = []\n",
    "\n",
    "        for node1, node2 in edges: # 有向边，从 node1 到 node2\n",
    "            if parent[node2] != node2:  # 不允许两个父节点\n",
    "                conflictEdge = (node1, node2)\n",
    "            elif findroot(node1) == findroot(node2):\n",
    "                cycle = (node1, node2)  # 产生环（根相同）\n",
    "            else:\n",
    "                parent[node2] = node1 # node2 的上一级是 node1\n",
    "\n",
    "\n",
    "        if not conflictEdge:  # 没有双父，就是环的边\n",
    "            return cycle\n",
    "        if cycle: # 只要有环，就是另一条边\n",
    "            return [parent[conflictEdge[1]], conflictEdge[1]]\n",
    "        # 没环，就是这条边\n",
    "        return conflictEdge\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #因为是只有N个点和N条边，所以只要判断连通性即可，有向不是很重要\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        self.degree = {}\n",
    "        Num2Degree = []\n",
    "        for i in range(len(edges)):\n",
    "            self.degree[i] = []\n",
    "        for i in range(len(edges)):\n",
    "            self.degree[edges[i][1]-1].append(i)\n",
    "            if len(self.degree[edges[i][1]-1]) == 2:\n",
    "                Num2Degree = self.degree[edges[i][1]-1][:]\n",
    "        # print(Num2Degree)\n",
    "        if not Num2Degree:\n",
    "            return edges[self.getRemoveEdge(edges)]\n",
    "        else:\n",
    "\n",
    "            for i in range(len(Num2Degree)-1,-1,-1):\n",
    "                # print(\"Num2Degree[i] is\",Num2Degree[i])\n",
    "                if self.isTreeAfterRemoveEdge(edges, Num2Degree[i]):\n",
    "                    return edges[Num2Degree[i]]\n",
    "    \n",
    "\n",
    "    \n",
    "\n",
    "\n",
    "    def isTreeAfterRemoveEdge(self, edges, delete_i):\n",
    "        self.father = [i for i in range(len(edges))]\n",
    "        for i in range(len(edges)):\n",
    "            if i != delete_i:\n",
    "                u = self.find(edges[i][0]-1)\n",
    "                v = self.find(edges[i][1]-1)\n",
    "                if u != v:\n",
    "                    self.father[v] = u\n",
    "                else:\n",
    "                    return False\n",
    "        return True\n",
    "\n",
    "    def getRemoveEdge(self, edges):\n",
    "        #有两种写法 一种是利用isTreeAfterRemoveEdge来判断，但需要从后往前遍历\n",
    "        #还有一种就是和无向图一样，从前往后构建并查集，最后一个输出即可\n",
    "        self.father = [i for i in range(len(edges))]\n",
    "        for i in range(len(edges)):\n",
    "            u = self.find(edges[i][0]-1)\n",
    "            v = self.find(edges[i][1]-1)\n",
    "            if u != v:\n",
    "                self.father[v] = u\n",
    "            else:\n",
    "                return i            \n",
    "        \n",
    "\n",
    "    def find(self, u):\n",
    "        if u == self.father[u]:\n",
    "            return u\n",
    "        else:\n",
    "            self.father[u] = self.find(self.father[u])\n",
    "            return self.father[u]\n",
    "    \n",
    "    def join(self, u, v):\n",
    "        u = self.find(u)\n",
    "        v = self.find(v)\n",
    "        if u != v:\n",
    "            self.father[v] = u\n",
    "        return\n",
    "\n",
    "    def isSame(self, u, v):\n",
    "        return self.find(u) == self.find(v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        innum = [0 for _ in range(n+1)]\n",
    "        for i in range(n):\n",
    "            innum[edges[i][1]] += 1\n",
    "        print(innum)\n",
    "        \n",
    "        # index = innum.index(2)\n",
    "        # print(index)\n",
    "        index = []\n",
    "        for i in range(n):\n",
    "            if innum[edges[i][1]] == 2:\n",
    "                index.append(i)\n",
    "        for i in index:\n",
    "            print(i)\n",
    "        if index:\n",
    "            for i in range(1,-1,-1):\n",
    "                father = [_ for _ in range(n+1)]\n",
    "                print('i, father', i, father)\n",
    "                for j in range(n):\n",
    "                    if j == index[i]:\n",
    "                        print('here, j', j)\n",
    "                        continue\n",
    "                    else:\n",
    "                        self.union(edges[j][0],edges[j][1],father)\n",
    "                if self.find(edges[index[i]][0],father) == self.find(edges[index[i]][1],father):\n",
    "                    print('current father', father, 'current edge', edges[i])\n",
    "                    return edges[index[i]]\n",
    "        else:\n",
    "            father = [_ for _ in range(n+1)]\n",
    "            for i in range(n):\n",
    "                if self.find(edges[i][0], father) == self.find(edges[i][1], father):\n",
    "                    return edges[i]\n",
    "                else:\n",
    "                    self.union(edges[i][0], edges[i][1], father)\n",
    "\n",
    "    def find(self, i, father):\n",
    "        if i == father[i]:\n",
    "            return i\n",
    "        else:\n",
    "            i = self.find(father[father[i]], father)\n",
    "        return father[i]\n",
    "        # 这里的return是为了将father传递给外部调用的部分\n",
    "\n",
    "    def union(self, i, j, father):\n",
    "        fa_i = self.find(i, father)\n",
    "        fa_j = self.find(j, father)\n",
    "        father[fa_i] = father[fa_j]\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.ancestor = list(range(n))\n",
    "    \n",
    "    def union(self, index1: int, index2: int):\n",
    "        self.ancestor[self.find(index1)] = self.find(index2)\n",
    "    \n",
    "    def find(self, index: int) -> int:\n",
    "        if self.ancestor[index] != index:\n",
    "            self.ancestor[index] = self.find(self.ancestor[index])\n",
    "        return self.ancestor[index]\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        uf = UnionFind(n + 1)\n",
    "        parent = list(range(n + 1))\n",
    "        conflict = -1\n",
    "        cycle = -1\n",
    "        for i, (node1, node2) in enumerate(edges):\n",
    "            if parent[node2] != node2:\n",
    "                conflict = i\n",
    "            else:\n",
    "                parent[node2] = node1\n",
    "                if uf.find(node1) == uf.find(node2):\n",
    "                    cycle = i\n",
    "                else:\n",
    "                    uf.union(node1, node2)\n",
    "\n",
    "        if conflict < 0:\n",
    "            return [edges[cycle][0], edges[cycle][1]]\n",
    "        else:\n",
    "            conflictEdge = edges[conflict]\n",
    "            if cycle >= 0:\n",
    "                return [parent[conflictEdge[1]], conflictEdge[1]]\n",
    "            else:\n",
    "                return [conflictEdge[0], conflictEdge[1]]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.n = 1010\n",
    "        self.father = [i for i in range(self.n)]\n",
    "\n",
    "\n",
    "    def find(self, u: int):\n",
    "        \"\"\"\n",
    "        并查集里寻根的过程\n",
    "        \"\"\"\n",
    "        if u == self.father[u]:\n",
    "            return u\n",
    "        self.father[u] = self.find(self.father[u])\n",
    "        return self.father[u]\n",
    "\n",
    "    def join(self, u: int, v: int):\n",
    "        \"\"\"\n",
    "        将v->u 这条边加入并查集\n",
    "        \"\"\"\n",
    "        u = self.find(u)\n",
    "        v = self.find(v)\n",
    "        if u == v : return\n",
    "        self.father[v] = u\n",
    "        pass\n",
    "\n",
    "\n",
    "    def same(self, u: int, v: int ):\n",
    "        \"\"\"\n",
    "        判断 u 和 v是否找到同一个根，本题用不上\n",
    "        \"\"\"\n",
    "        u = self.find(u)\n",
    "        v = self.find(v)\n",
    "        return u == v\n",
    "\n",
    "    def init_father(self):\n",
    "        self.father = [i for i in range(self.n)]\n",
    "        pass\n",
    "\n",
    "    def getRemoveEdge(self, edges: List[List[int]]) -> List[int]:\n",
    "        \"\"\"\n",
    "        在有向图里找到删除的那条边，使其变成树\n",
    "        \"\"\"\n",
    "\n",
    "        self.init_father()\n",
    "        for i in range(len(edges)):\n",
    "            if self.same(edges[i][0], edges[i][1]): # 构成有向环了，就是要删除的边\n",
    "                return edges[i]\n",
    "            self.join(edges[i][0], edges[i][1]);\n",
    "        return []\n",
    "\n",
    "    def isTreeAfterRemoveEdge(self, edges: List[List[int]], deleteEdge: int) -> bool:\n",
    "        \"\"\"\n",
    "        删一条边之后判断是不是树\n",
    "        \"\"\"\n",
    "\n",
    "        self.init_father()\n",
    "        for i in range(len(edges)):\n",
    "            if i == deleteEdge: continue\n",
    "            if self.same(edges[i][0], edges[i][1]): #  构成有向环了，一定不是树\n",
    "                return False\n",
    "            self.join(edges[i][0], edges[i][1]);\n",
    "        return True\n",
    "\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        inDegree = [0 for i in range(self.n)]\n",
    "\n",
    "        for i in range(len(edges)):\n",
    "            inDegree[ edges[i][1] ] += 1\n",
    "\n",
    "        # 找入度为2的节点所对应的边，注意要倒序，因为优先返回最后出现在二维数组中的答案\n",
    "        towDegree = []\n",
    "        for i in range(len(edges))[::-1]:\n",
    "            if inDegree[edges[i][1]] == 2 :\n",
    "                towDegree.append(i)\n",
    "\n",
    "        # 处理图中情况1 和 情况2\n",
    "        # 如果有入度为2的节点，那么一定是两条边里删一个，看删哪个可以构成树\n",
    "        if len(towDegree) > 0:\n",
    "            if(self.isTreeAfterRemoveEdge(edges, towDegree[0])) :\n",
    "                return edges[towDegree[0]]\n",
    "            return edges[towDegree[1]]\n",
    "\n",
    "        # 明确没有入度为2的情况，那么一定有有向环，找到构成环的边返回就可以了\n",
    "        return self.getRemoveEdge(edges)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #因为是只有N个点和N条边，所以只要判断连通性即可，有向不是很重要\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        self.degree = {}\n",
    "        Num2Degree = []\n",
    "        for i in range(len(edges)):\n",
    "            self.degree[i] = []\n",
    "        for i in range(len(edges)):\n",
    "            self.degree[edges[i][1]-1].append(i)\n",
    "            if len(self.degree[edges[i][1]-1]) == 2:\n",
    "                Num2Degree = self.degree[edges[i][1]-1][:]\n",
    "        # print(Num2Degree)\n",
    "        if not Num2Degree:\n",
    "            return edges[self.getRemoveEdge(edges)]\n",
    "        else:\n",
    "\n",
    "            for i in range(len(Num2Degree)-1,-1,-1):\n",
    "                # print(\"Num2Degree[i] is\",Num2Degree[i])\n",
    "                if self.isTreeAfterRemoveEdge(edges, Num2Degree[i]):\n",
    "                    return edges[Num2Degree[i]]\n",
    "    \n",
    "\n",
    "    \n",
    "\n",
    "\n",
    "    def isTreeAfterRemoveEdge(self, edges, delete_i):\n",
    "        self.father = [i for i in range(len(edges))]\n",
    "        for i in range(len(edges)):\n",
    "            if i != delete_i:\n",
    "                u = self.find(edges[i][0]-1)\n",
    "                v = self.find(edges[i][1]-1)\n",
    "                if u != v:\n",
    "                    self.father[v] = u\n",
    "                else:\n",
    "                    return False\n",
    "        return True\n",
    "\n",
    "    def getRemoveEdge(self, edges):\n",
    "        #有两种写法 一种是利用isTreeAfterRemoveEdge来判断，但需要从后往前遍历\n",
    "        #还有一种就是和无向图一样，从前往后构建并查集，最后一个输出即可 (更快一点)\n",
    "        self.father = [i for i in range(len(edges))]\n",
    "        for i in range(len(edges)):\n",
    "            u = self.find(edges[i][0]-1)\n",
    "            v = self.find(edges[i][1]-1)\n",
    "            if u != v:\n",
    "                self.father[v] = u\n",
    "            else:\n",
    "                return i            \n",
    "        \n",
    "\n",
    "    def find(self, u):\n",
    "        if u == self.father[u]:\n",
    "            return u\n",
    "        else:\n",
    "            self.father[u] = self.find(self.father[u])\n",
    "            return self.father[u]\n",
    "    \n",
    "    def join(self, u, v):\n",
    "        u = self.find(u)\n",
    "        v = self.find(v)\n",
    "        if u != v:\n",
    "            self.father[v] = u\n",
    "        return\n",
    "\n",
    "    def isSame(self, u, v):\n",
    "        return self.find(u) == self.find(v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        #初始化祖先为自身，即无祖先\n",
    "        self.ancestor = list(range(n))\n",
    "    # 将index1所在的集合加入到index2的集合中\n",
    "    def union(self, index1: int, index2: int):\n",
    "        #index1的祖先的祖先设置为index2的祖先\n",
    "        self.ancestor[self.find(index1)] = self.find(index2)\n",
    "    # 找到祖先\n",
    "    def find(self, index: int) -> int:\n",
    "        if self.ancestor[index] != index:\n",
    "            self.ancestor[index] = self.find(self.ancestor[index])\n",
    "        return self.ancestor[index]\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        # 辅助数组parent以及并查集初始化\n",
    "        nodesCount = len(edges)\n",
    "        uf = UnionFind(nodesCount + 1)#现在所有结点都暂无祖先\n",
    "        parent = list(range(nodesCount + 1))#父节点也都是自己本身\n",
    "        # 冲突/环标签\n",
    "        conflict = -1\n",
    "        cycle = -1\n",
    "        # 开始遍历\n",
    "        for i, (node1, node2) in enumerate(edges):\n",
    "            if parent[node2] != node2:  # 产生冲突（有两个父节点）\n",
    "                conflict = i\n",
    "                continue\n",
    "            parent[node2] = node1\n",
    "            if uf.find(node1) == uf.find(node2):\n",
    "                cycle = i  # 产生环（祖先相同）\n",
    "            else:\n",
    "                uf.union(node1, node2)  # 合并，就是一点一点延长树\n",
    "        # 获取有问题的边\n",
    "        if conflict < 0:  # 没有冲突就是环的边\n",
    "            return [edges[cycle][0], edges[cycle][1]]\n",
    "        conflictEdge = edges[conflict]\n",
    "        if cycle >= 0:\n",
    "            return [parent[conflictEdge[1]], conflictEdge[1]]  # 环存在，并且冲突也存在，优先删除在环上的边\n",
    "        return [conflictEdge[0], conflictEdge[1]]  # 无环就是冲突边"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.n = 1010\n",
    "        self.father = [i for i in range(self.n)]\n",
    "\n",
    "    def find(self, u:int):\n",
    "        # 并查集里寻根的过程\n",
    "        if u == self.father[u]:\n",
    "            return u\n",
    "        self.father[u] = self.find(self.father[u])\n",
    "        return self.father[u]\n",
    "\n",
    "    def join(self, u:int, v:int):\n",
    "        # 将v->u 这条边加入并查集\n",
    "        u = self.find(u)\n",
    "        v = self.find(v)\n",
    "        if u == v:\n",
    "            return\n",
    "        self.father[v] = u\n",
    "        pass\n",
    "\n",
    "    def same(self, u:int, v:int):\n",
    "        # 判断u和v是否找到同一个根（本题用不上）\n",
    "        u = self.find(u)\n",
    "        v = self.find(v)\n",
    "        return u == v\n",
    "\n",
    "    def init_father(self):\n",
    "        self.father = [i for i in range(self.n)]\n",
    "        pass\n",
    "\n",
    "    def getRemoveEdge(self, edges:List[List[int]]) -> List[int]:\n",
    "        # 在有向图里找到删除的那条边，使其变成树\n",
    "        self.init_father()\n",
    "        for i in range(len(edges)):\n",
    "            if self.same(edges[i][0], edges[i][1]):\n",
    "                return edges[i]\n",
    "            self.join(edges[i][0], edges[i][1]);\n",
    "        return []\n",
    "\n",
    "    def isTreeAfterRemoveEdge(self, edges: List[List[int]], deleteEdge:int) -> bool:\n",
    "        # 删一条边之后判断是不是树\n",
    "        self.init_father()\n",
    "        for i in range(len(edges)):\n",
    "            if i == deleteEdge: continue\n",
    "            if self.same(edges[i][0], edges[i][1]):\n",
    "                return False\n",
    "            self.join(edges[i][0], edges[i][1])\n",
    "        return True\n",
    "\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        inDegree = [0 for i in range(self.n)]\n",
    "\n",
    "        for i in range(len(edges)):\n",
    "            inDegree[edges[i][1]] += 1\n",
    "        towDegree = []\n",
    "\n",
    "        for i in range(len(edges))[::-1]:\n",
    "            if inDegree[edges[i][1]] == 2:\n",
    "                towDegree.append(i)\n",
    "\n",
    "        if len(towDegree) > 0:\n",
    "            if(self.isTreeAfterRemoveEdge(edges, towDegree[0])):\n",
    "                return edges[towDegree[0]]\n",
    "            return edges[towDegree[1]]\n",
    "\n",
    "        return self.getRemoveEdge(edges)\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        indeg = [0] * (n+1)\n",
    "        outdeg = [0] * (n+1)\n",
    "        s_edges = set()\n",
    "\n",
    "        for e in edges:\n",
    "            u = e[0]\n",
    "            v = e[1]\n",
    "\n",
    "            indeg[v] += 1\n",
    "            outdeg[u] += 1\n",
    "\n",
    "            s_edges.add((u, v))\n",
    "\n",
    "        no_multiparent = True\n",
    "        mpnode = 0\n",
    "\n",
    "\n",
    "\n",
    "        for node in range(1, n+1):\n",
    "            d = indeg[node]\n",
    "            if d > 1:\n",
    "                no_multiparent = False\n",
    "                mpnode = node\n",
    "                break\n",
    "\n",
    "        # handle corner case: exact opposite edge pair (e.g. [1, 2] and [2, 1])\n",
    "        for e in edges[::-1]:\n",
    "            u = e[0]\n",
    "            v = e[1]\n",
    "\n",
    "            if (v, u) in s_edges:\n",
    "                if outdeg[u] > outdeg[v] or indeg[u] < indeg[v]:\n",
    "                    return [u, v]\n",
    "                return [v, u]\n",
    "\n",
    "        # regular handling: try to find 1st candidate edge to be removed (and check it's able to eliminate multiparent case, if it existed)\n",
    "        for e in edges[::-1]:\n",
    "            u = e[0]\n",
    "            v = e[1]\n",
    "\n",
    "            if indeg[u] + outdeg[u] > 1 and indeg[v] + outdeg[v] > 1 and (no_multiparent or mpnode == v):\n",
    "                return [u, v]\n",
    "\n",
    "\n",
    "        return [-1, -1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        def find(u):\n",
    "            if u == self.f[u]:\n",
    "                return u\n",
    "            self.f[u] = find(self.f[u])\n",
    "            return self.f[u]\n",
    "\n",
    "        def join(u, v):\n",
    "            u, v = find(u), find(v)\n",
    "            if u == v:\n",
    "                return\n",
    "            self.f[v] = u\n",
    "\n",
    "        def same(u, v):\n",
    "            u, v = find(u), find(v)\n",
    "            return u == v\n",
    "\n",
    "        def wrongEdge(edges, ex):\n",
    "            self.f = [i for i in range(self.n + 1)]\n",
    "            for u, v in edges:\n",
    "                if [u, v] == ex:\n",
    "                    continue\n",
    "                if same(u, v):\n",
    "                    return [u, v]\n",
    "                join(u, v)\n",
    "            return []\n",
    "\n",
    "        self.n = len(edges)\n",
    "        self.degree = [0] * (self.n + 1)\n",
    "        for u, v in edges:\n",
    "            self.degree[v] += 1\n",
    "        for u, v in edges[::-1]:\n",
    "            if self.degree[v] == 2 and len(wrongEdge(edges, [u, v])) == 0:\n",
    "                return [u, v]\n",
    "        return wrongEdge(edges, [])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.n = 1010\n",
    "        self.father = [i for i in range(self.n)]\n",
    "\n",
    "\n",
    "    def find(self, u: int):\n",
    "        \"\"\"\n",
    "        并查集里寻根的过程\n",
    "        \"\"\"\n",
    "        if u == self.father[u]:\n",
    "            return u\n",
    "        self.father[u] = self.find(self.father[u])\n",
    "        return self.father[u]\n",
    "\n",
    "    def join(self, u: int, v: int):\n",
    "        \"\"\"\n",
    "        将v->u 这条边加入并查集\n",
    "        \"\"\"\n",
    "        u = self.find(u)\n",
    "        v = self.find(v)\n",
    "        if u == v : return\n",
    "        self.father[v] = u\n",
    "        pass\n",
    "\n",
    "\n",
    "    def same(self, u: int, v: int ):\n",
    "        \"\"\"\n",
    "        判断 u 和 v是否找到同一个根，本题用不上\n",
    "        \"\"\"\n",
    "        u = self.find(u)\n",
    "        v = self.find(v)\n",
    "        return u == v\n",
    "\n",
    "    def init_father(self):\n",
    "        self.father = [i for i in range(self.n)]\n",
    "        pass\n",
    "\n",
    "    def getRemoveEdge(self, edges: List[List[int]]) -> List[int]:\n",
    "        \"\"\"\n",
    "        在有向图里找到删除的那条边，使其变成树\n",
    "        \"\"\"\n",
    "\n",
    "        self.init_father()\n",
    "        for i in range(len(edges)):\n",
    "            if self.same(edges[i][0], edges[i][1]): # 构成有向环了，就是要删除的边\n",
    "                return edges[i]\n",
    "            self.join(edges[i][0], edges[i][1]);\n",
    "        return []\n",
    "\n",
    "    def isTreeAfterRemoveEdge(self, edges: List[List[int]], deleteEdge: int) -> bool:\n",
    "        \"\"\"\n",
    "        删一条边之后判断是不是树\n",
    "        \"\"\"\n",
    "\n",
    "        self.init_father()\n",
    "        for i in range(len(edges)):\n",
    "            if i == deleteEdge: continue\n",
    "            if self.same(edges[i][0], edges[i][1]): #  构成有向环了，一定不是树\n",
    "                return False\n",
    "            self.join(edges[i][0], edges[i][1]);\n",
    "        return True\n",
    "\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        inDegree = [0 for i in range(self.n)]\n",
    "\n",
    "        for i in range(len(edges)):\n",
    "            inDegree[ edges[i][1] ] += 1\n",
    "\n",
    "        # 找入度为2的节点所对应的边，注意要倒序，因为优先返回最后出现在二维数组中的答案\n",
    "        towDegree = []\n",
    "        for i in range(len(edges))[::-1]:\n",
    "            if inDegree[edges[i][1]] == 2 :\n",
    "                towDegree.append(i)\n",
    "\n",
    "        # 处理图中情况1 和 情况2\n",
    "        # 如果有入度为2的节点，那么一定是两条边里删一个，看删哪个可以构成树\n",
    "        if len(towDegree) > 0:\n",
    "            if(self.isTreeAfterRemoveEdge(edges, towDegree[0])) :\n",
    "                return edges[towDegree[0]]\n",
    "            return edges[towDegree[1]]\n",
    "\n",
    "        # 明确没有入度为2的情况，那么一定有有向环，找到构成环的边返回就可以了\n",
    "        return self.getRemoveEdge(edges)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.n = 1001\n",
    "        self.father = [i for i in range(self.n)]\n",
    "    \n",
    "    def find(self,i):\n",
    "        if self.father[i] != i:\n",
    "            self.father[i] = self.find(self.father[i])\n",
    "        return self.father[i]\n",
    "    \n",
    "    def join(self,u, v):\n",
    "        self.father[self.find(u)] = self.find(v)\n",
    "        return \n",
    "    \n",
    "    def same(self,u, v):\n",
    "        return self.find(u) == self.find(v)\n",
    "\n",
    "    def init_father(self,):\n",
    "        self.father = [i for i in range(self.n)]\n",
    "\n",
    "    def getRemoveEdge(self, edges: List[List[int]]) -> List[int]:\n",
    "        self.init_father()\n",
    "        for i in range(len(edges)):\n",
    "            if self.same(edges[i][0], edges[i][1]):\n",
    "                return edges[i]\n",
    "            self.join(edges[i][0], edges[i][1]);\n",
    "        return \n",
    "    \n",
    "    def isTreeAfterRemoveEdge(self, edges: List[List[int]], deleteEdge: int) -> bool:\n",
    "        self.init_father()\n",
    "        for i in range(len(edges)):\n",
    "            if i == deleteEdge: continue\n",
    "            if self.same(edges[i][0], edges[i][1]):\n",
    "                return False\n",
    "            self.join(edges[i][0], edges[i][1])\n",
    "        return True\n",
    "\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        inDegree = [0 for i in range(self.n)]\n",
    "\n",
    "        for i in range(len(edges)):\n",
    "            inDegree[edges[i][1]] += 1\n",
    "\n",
    "        towDegree = []\n",
    "        for i in range(len(edges))[::-1]:\n",
    "            if inDegree[edges[i][1]] == 2 :\n",
    "                towDegree.append(i)\n",
    "\n",
    "        if len(towDegree) > 0:\n",
    "            if(self.isTreeAfterRemoveEdge(edges, towDegree[0])) :\n",
    "                return edges[towDegree[0]]\n",
    "            return edges[towDegree[1]]\n",
    "\n",
    "        return self.getRemoveEdge(edges)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        indeg = [0] * (n+1)\n",
    "        outdeg = [0] * (n+1)\n",
    "        s_edges = set()\n",
    "\n",
    "        for e in edges:\n",
    "            u = e[0]\n",
    "            v = e[1]\n",
    "\n",
    "            indeg[v] += 1\n",
    "            outdeg[u] += 1\n",
    "\n",
    "            s_edges.add((u, v))\n",
    "\n",
    "        no_multiparent = True\n",
    "        mpnode = 0\n",
    "\n",
    "\n",
    "\n",
    "        for node in range(1, n+1):\n",
    "            d = indeg[node]\n",
    "            if d > 1:\n",
    "                no_multiparent = False\n",
    "                mpnode = node\n",
    "                break\n",
    "\n",
    "        for e in edges[::-1]:\n",
    "            u = e[0]\n",
    "            v = e[1]\n",
    "\n",
    "            if (v, u) in s_edges:\n",
    "                if outdeg[u] > outdeg[v]: return [u, v]\n",
    "                if mpnode == v: return [u, v]\n",
    "                return [v, u]\n",
    "\n",
    "        for e in edges[::-1]:\n",
    "            u = e[0]\n",
    "            v = e[1]\n",
    "\n",
    "            if indeg[u] + outdeg[u] > 1 and indeg[v] + outdeg[v] > 1 and (no_multiparent or mpnode == v):\n",
    "                return [u, v]\n",
    "\n",
    "\n",
    "        return [-1, -1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.n = 1001\n",
    "        self.father = [i for i in range(self.n)]\n",
    "    \n",
    "    def find(self,i):\n",
    "        if self.father[i] != i:\n",
    "            self.father[i] = self.find(self.father[i])\n",
    "        return self.father[i]\n",
    "    \n",
    "    def join(self,u, v):\n",
    "        self.father[self.find(u)] = self.find(v)\n",
    "        return \n",
    "    \n",
    "    def same(self,u, v):\n",
    "        return self.find(u) == self.find(v)\n",
    "\n",
    "    def init_father(self,):\n",
    "        self.father = [i for i in range(self.n)]\n",
    "\n",
    "    def getRemoveEdge(self, edges: List[List[int]]) -> List[int]:\n",
    "        self.init_father()\n",
    "        for i in range(len(edges)):\n",
    "            if self.same(edges[i][0], edges[i][1]):\n",
    "                return edges[i]\n",
    "            self.join(edges[i][0], edges[i][1]);\n",
    "        return \n",
    "    \n",
    "    def isTreeAfterRemoveEdge(self, edges: List[List[int]], deleteEdge: int) -> bool:\n",
    "        self.init_father()\n",
    "        for i in range(len(edges)):\n",
    "            if i == deleteEdge: continue\n",
    "            if self.same(edges[i][0], edges[i][1]):\n",
    "                return False\n",
    "            self.join(edges[i][0], edges[i][1]);\n",
    "        return True\n",
    "\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        inDegree = [0 for i in range(self.n)]\n",
    "\n",
    "        for i in range(len(edges)):\n",
    "            inDegree[edges[i][1]] += 1\n",
    "\n",
    "        towDegree = []\n",
    "        for i in range(len(edges))[::-1]:\n",
    "            if inDegree[edges[i][1]] == 2 :\n",
    "                towDegree.append(i)\n",
    "\n",
    "        if len(towDegree) > 0:\n",
    "            if(self.isTreeAfterRemoveEdge(edges, towDegree[0])) :\n",
    "                return edges[towDegree[0]]\n",
    "            return edges[towDegree[1]]\n",
    "\n",
    "        return self.getRemoveEdge(edges)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.n = 1010\n",
    "        self.father = [i for i in range(self.n)]\n",
    "\n",
    "\n",
    "    def find(self, u: int):\n",
    "        \"\"\"\n",
    "        并查集里寻根的过程\n",
    "        \"\"\"\n",
    "        if u == self.father[u]:\n",
    "            return u\n",
    "        self.father[u] = self.find(self.father[u])\n",
    "        return self.father[u]\n",
    "\n",
    "    def join(self, u: int, v: int):\n",
    "        \"\"\"\n",
    "        将v->u 这条边加入并查集\n",
    "        \"\"\"\n",
    "        u = self.find(u)\n",
    "        v = self.find(v)\n",
    "        if u == v : return\n",
    "        self.father[v] = u\n",
    "        pass\n",
    "\n",
    "\n",
    "    def same(self, u: int, v: int ):\n",
    "        \"\"\"\n",
    "        判断 u 和 v是否找到同一个根，本题用不上\n",
    "        \"\"\"\n",
    "        u = self.find(u)\n",
    "        v = self.find(v)\n",
    "        return u == v\n",
    "\n",
    "    def init_father(self):\n",
    "        self.father = [i for i in range(self.n)]\n",
    "        pass\n",
    "\n",
    "    def getRemoveEdge(self, edges: List[List[int]]) -> List[int]:\n",
    "        \"\"\"\n",
    "        在有向图里找到删除的那条边，使其变成树\n",
    "        \"\"\"\n",
    "\n",
    "        self.init_father()\n",
    "        for i in range(len(edges)):\n",
    "            if self.same(edges[i][0], edges[i][1]): # 构成有向环了，就是要删除的边\n",
    "                return edges[i]\n",
    "            self.join(edges[i][0], edges[i][1]);\n",
    "        return []\n",
    "\n",
    "    def isTreeAfterRemoveEdge(self, edges: List[List[int]], deleteEdge: int) -> bool:\n",
    "        \"\"\"\n",
    "        删一条边之后判断是不是树\n",
    "        \"\"\"\n",
    "\n",
    "        self.init_father()\n",
    "        for i in range(len(edges)):\n",
    "            if i == deleteEdge: continue\n",
    "            if self.same(edges[i][0], edges[i][1]): #  构成有向环了，一定不是树\n",
    "                return False\n",
    "            self.join(edges[i][0], edges[i][1]);\n",
    "        return True\n",
    "\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        inDegree = [0 for i in range(self.n)]\n",
    "\n",
    "        for i in range(len(edges)):\n",
    "            inDegree[ edges[i][1] ] += 1\n",
    "\n",
    "        # 找入度为2的节点所对应的边，注意要倒序，因为优先返回最后出现在二维数组中的答案\n",
    "        towDegree = []\n",
    "        for i in range(len(edges))[::-1]:\n",
    "            if inDegree[edges[i][1]] == 2 :\n",
    "                towDegree.append(i)\n",
    "\n",
    "        # 处理图中情况1 和 情况2\n",
    "        # 如果有入度为2的节点，那么一定是两条边里删一个，看删哪个可以构成树\n",
    "        if len(towDegree) > 0:\n",
    "            if(self.isTreeAfterRemoveEdge(edges, towDegree[0])) :\n",
    "                return edges[towDegree[0]]\n",
    "            return edges[towDegree[1]]\n",
    "\n",
    "        # 明确没有入度为2的情况，那么一定有有向环，找到构成环的边返回就可以了\n",
    "        return self.getRemoveEdge(edges)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        # 一共两种情况，1：两条边指向同一个结点，必有一个是多余的 2：有环\n",
    "\n",
    "        # 先找有没有两条边指向同一个结点\n",
    "        a = []\n",
    "        overleap_line = -1\n",
    "        for line in edges:\n",
    "            if line[1] in a:\n",
    "                overleap_line = line[1]\n",
    "                break\n",
    "            a.append(line[1])\n",
    "        del a\n",
    "\n",
    "        num_to_line = dict()\n",
    "        for i in range(len(edges)):\n",
    "            num_to_line[i+1] = []\n",
    "        for line_s, line_e in edges:\n",
    "            num_to_line[line_s].append([line_s, line_e])\n",
    "            num_to_line[line_e].append([line_s, line_e])\n",
    "\n",
    "        # 去掉叶子结点简化结构\n",
    "        while True:\n",
    "            one_line = []\n",
    "            for key in num_to_line:\n",
    "                if len(num_to_line[key]) == 1:\n",
    "                    one_line.append(num_to_line[key][0])\n",
    "            if len(one_line) == 0:\n",
    "                if overleap_line != -1: # 属于第一种情况\n",
    "                    for i in range(len(num_to_line[overleap_line])-1, -1, -1):\n",
    "                        line = num_to_line[overleap_line][i]\n",
    "                        if line[1] != overleap_line:\n",
    "                            continue\n",
    "                        if len(num_to_line[line[0]]) != 1:\n",
    "                            return  line\n",
    "                else:\n",
    "                    return edges[-1] # 属于第二种情况\n",
    "\n",
    "            while len(one_line) != 0:\n",
    "                line_s, line_e = one_line.pop()\n",
    "                edges.remove([line_s, line_e])\n",
    "                num_to_line[line_s].remove([line_s, line_e])\n",
    "                num_to_line[line_e].remove([line_s, line_e])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Union(object):\n",
    "    def __init__(self, num_nodes):\n",
    "        self.num_connected=num_nodes\n",
    "        self.tree_nodes=[1 for i in range(num_nodes)]\n",
    "        self.tree_root=[i for i in range(num_nodes)]\n",
    "\n",
    "    def union(self,x,y):\n",
    "        r_x=self.find(x)\n",
    "        r_y=self.find(y)\n",
    "        if r_x==r_y:\n",
    "            return\n",
    "        if self.tree_nodes[r_x]<self.tree_nodes[r_y]:\n",
    "            self.tree_nodes[r_x]+=self.tree_nodes[r_y]\n",
    "            self.tree_root[x]=self.tree_root[r_x]\n",
    "            self.tree_root[y]=self.tree_root[r_x]\n",
    "        else:\n",
    "            self.tree_nodes[r_x]+=self.tree_nodes[r_y]\n",
    "            self.tree_root[x]=self.tree_root[r_y]\n",
    "            self.tree_root[y]=self.tree_root[r_y]\n",
    "        self.num_connected-=1\n",
    "    \n",
    "    def find(self,x):\n",
    "        while x!=self.tree_root[x]:\n",
    "            x=self.tree_root[x]\n",
    "        return x\n",
    "    \n",
    "    def connected(self,x,y):\n",
    "        return self.find(x)==self.find(y)\n",
    "    \n",
    "\n",
    "class Solution:\n",
    "    # 判断删一个边之后是不是树了\n",
    "    def is_Tree_afterRemoveEdge(self, edges, removed_edge_index):\n",
    "        tree = Union(len(edges)+1)\n",
    "        for i in range(len(edges)):\n",
    "            x, y=edges[i]    \n",
    "            if i==removed_edge_index:\n",
    "               continue\n",
    "            if tree.connected(x,y):\n",
    "                return False\n",
    "            tree.union(x,y)\n",
    "        return True\n",
    "\n",
    "    # 在有向图里找到删除的那条边，使其变成树，返回值就是要删除的边\n",
    "    def getRemoveEdge(self, edges):\n",
    "        tree = Union(len(edges) + 1)  # 初始化并查集\n",
    "        for i in range(len(edges)):\n",
    "            x, y = edges[i]\n",
    "            if tree.connected(x,y):\n",
    "                return [x,y]\n",
    "            tree.union(x, y)\n",
    "        return []\n",
    "\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n=len(edges)\n",
    "        in_degree=[0 for i in range(n+1)]\n",
    "        for x,y in edges:\n",
    "            in_degree[y]+=1\n",
    "            if in_degree[y]==2:\n",
    "                    break\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if edges[i][1]==y:\n",
    "                if self.is_Tree_afterRemoveEdge(edges,i):\n",
    "                    return edges[i]\n",
    "        return self.getRemoveEdge(edges)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        father = [[] for _ in range(len(edges) + 1)]\n",
    "        son = [set() for _ in range(len(edges) + 1)]\n",
    "        for edge in edges:\n",
    "            father[edge[1]].append(edge[0])\n",
    "            son[edge[0]].add(edge[1])\n",
    "\n",
    "        def bfs(a, b):\n",
    "            t = set()\n",
    "            t.add(a)\n",
    "            p = []\n",
    "            for r in father[a]:\n",
    "                if r != b:\n",
    "                    p.append(r)\n",
    "                    t.add(r)\n",
    "            for r in son[a]:\n",
    "                p.append(r)\n",
    "                t.add(r)\n",
    "            while p:\n",
    "                x = p.pop()\n",
    "                for r in father[x]:\n",
    "                    if r not in t:\n",
    "                        p.append(r)\n",
    "                        t.add(r)\n",
    "                for r in son[x]:\n",
    "                    if r not in t:\n",
    "                        p.append(r)\n",
    "                        t.add(r)\n",
    "            return len(t) == len(edges)\n",
    "        for i in range(1, len(edges) + 1):\n",
    "            if len(father[i]) == 2:\n",
    "                x = father[i][1]\n",
    "                if bfs(i, x):\n",
    "                    return [father[i][1], i]\n",
    "                else:\n",
    "                    return [father[i][0], i]\n",
    "        test = []\n",
    "        for i in range(1, len(edges) + 1):\n",
    "            if not son[i]:\n",
    "                test.append(i)\n",
    "        while test:\n",
    "            x = test.pop()\n",
    "            for i in father[x]:\n",
    "                son[i].remove(x)\n",
    "                if not son[i]:\n",
    "                    test.append(i)\n",
    "        s = set()\n",
    "        for i in range(1, len(edges) + 1):\n",
    "            if son[i]:\n",
    "                s.add(i)\n",
    "        for i in range(len(edges) - 1, -1, -1):\n",
    "            if edges[i][0] in s and edges[i][1] in s:\n",
    "                return edges[i]\n",
    "        return []\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        # 一共两种情况，1：两条边指向同一个结点，必有一个是多余的 2：有环\n",
    "\n",
    "        # 先找有没有两条边指向同一个结点\n",
    "        a = []\n",
    "        overleap_line = -1\n",
    "        for line in edges:\n",
    "            if line[1] in a:\n",
    "                overleap_line = line[1]\n",
    "                break\n",
    "            a.append(line[1])\n",
    "        del a\n",
    "\n",
    "        num_to_line = dict()\n",
    "        for i in range(len(edges)):\n",
    "            num_to_line[i+1] = []\n",
    "\n",
    "        for line_s, line_e in edges:\n",
    "            num_to_line[line_s].append([line_s, line_e])\n",
    "            num_to_line[line_e].append([line_s, line_e])\n",
    "\n",
    "        # if overleap_line != -1: # 属于第一种情况\n",
    "        #     for i in range(len(num_to_line[overleap_line])-1, -1, -1):\n",
    "        #         line = num_to_line[overleap_line][i]\n",
    "        #         if line[1] != overleap_line:\n",
    "        #             continue\n",
    "        #         if len(num_to_line[line[0]]) != 1:\n",
    "        #             return  line\n",
    "\n",
    "        while True:\n",
    "            one_line = []\n",
    "            for key in num_to_line:\n",
    "                if len(num_to_line[key]) == 1:\n",
    "                    one_line.append(num_to_line[key][0])\n",
    "            if len(one_line) == 0:\n",
    "                if overleap_line != -1: # 属于第一种情况\n",
    "                    for i in range(len(num_to_line[overleap_line])-1, -1, -1):\n",
    "                        line = num_to_line[overleap_line][i]\n",
    "                        if line[1] != overleap_line:\n",
    "                            continue\n",
    "                        if len(num_to_line[line[0]]) != 1:\n",
    "                            return  line\n",
    "\n",
    "                return edges[-1]\n",
    "\n",
    "            while len(one_line) != 0:\n",
    "                line_s, line_e = one_line.pop()\n",
    "                edges.remove([line_s, line_e])\n",
    "                num_to_line[line_s].remove([line_s, line_e])\n",
    "                num_to_line[line_e].remove([line_s, line_e])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.n=1005\n",
    "        self.father=[i for i in range(self.n)]\n",
    "    def find(self, u):\n",
    "        if self.father[u]==u:\n",
    "            return u\n",
    "        self.father[u]=self.find(self.father[u])\n",
    "        return self.father[u]\n",
    "    def join(self, u, v):\n",
    "        u=self.find(u)\n",
    "        v=self.find(v)\n",
    "        if u==v:\n",
    "            return\n",
    "        self.father[v]=u\n",
    "    def same(self, u, v):\n",
    "        u=self.find(u)\n",
    "        v=self.find(v)\n",
    "        if u==v:\n",
    "            return True\n",
    "        return False\n",
    "    def init_father(self):\n",
    "        self.father=[i for i in range(self.n)]\n",
    "    def isTree(self, edges, deleteEdge):\n",
    "        self.init_father()\n",
    "        for i, (u, v) in enumerate(edges):\n",
    "            if i==deleteEdge:\n",
    "                continue\n",
    "            if self.same(u, v):# 一条边的两个节点有同一个祖先，构成有向图\n",
    "                return False\n",
    "            self.join(u, v)\n",
    "        return True\n",
    "    def getRemoveEdge(self, edges):\n",
    "        self.init_father()\n",
    "        for u, v in edges:\n",
    "            if self.same(u, v):\n",
    "                return [u, v]\n",
    "            self.join(u, v)\n",
    "        return []\n",
    "\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        # 统计入度\n",
    "        indegree=[0 for _ in range(self.n)]\n",
    "        for u, v in edges:\n",
    "            indegree[v]+=1\n",
    "        edgeTowDegree=[]\n",
    "        for i, (u, v) in enumerate(edges[::-1]):\n",
    "            if indegree[v]==2:\n",
    "                edgeTowDegree.append(len(edges)-i-1)\n",
    "        # 对于入度为2的节点：删除连接的其中一条边，使得删除后为树\n",
    "        if len(edgeTowDegree)>0:# 有入度为2，分为两种情况\n",
    "            if self.isTree(edges, edgeTowDegree[0]):\n",
    "                return edges[edgeTowDegree[0]]\n",
    "            return edges[edgeTowDegree[1]]\n",
    "        return self.getRemoveEdge(edges)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parents = [i for i in range(n)]\n",
    "        self.size = n\n",
    "    def find(self, p):\n",
    "        if self.parents[p] != p:\n",
    "            self.parents[p] = self.find(self.parents[p])\n",
    "        return self.parents[p]\n",
    "    def is_connected(self, p, q):\n",
    "        return self.find(p) == self.find(q)\n",
    "    def union(self, p, q):\n",
    "        if not self.is_connected(p, q):\n",
    "            p_p = self.find(p)\n",
    "            p_q = self.find(q)\n",
    "            self.parents[p_p] = p_q\n",
    "            self.size -= 1\n",
    "    def reset(self):\n",
    "        self.__init__(len(self.parents))\n",
    "    def check(self, edges, excluded):\n",
    "        self.reset()\n",
    "        for a, b in edges:\n",
    "            if [a, b] == excluded:\n",
    "                continue\n",
    "            self.union(b-1, a-1)\n",
    "        return self.size == 1\n",
    "        \n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        uf = UnionFind(n)\n",
    "        graph = [[] for _ in range(n)]\n",
    "        reverse_graph = [[]for _ in range(n)]\n",
    "        in_degrees = [0]*n\n",
    "        for a, b in edges:\n",
    "            graph[a-1].append(b-1)\n",
    "            reverse_graph[b-1].append(a-1)\n",
    "            in_degrees[b-1] += 1\n",
    "            if in_degrees[b-1] == 2:\n",
    "                if uf.check(edges, [a, b]):\n",
    "                    return [a, b]\n",
    "                else:\n",
    "                    return [reverse_graph[b-1][0]+1, b]\n",
    "        uf.reset()\n",
    "        for a, b in edges:\n",
    "            if uf.is_connected(a-1, b-1):\n",
    "                return [a, b]\n",
    "            else:\n",
    "                uf.union(b-1, a-1)\n",
    "                \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = max(max(x) for x in edges)\n",
    "        l_in = [0 for _ in range(n+1)]\n",
    "        l_out = [0 for _ in range(n+1)]\n",
    "        d_graph = defaultdict(list)\n",
    "        d_graph2 = defaultdict(set)\n",
    "        for i, j in edges:\n",
    "            l_in[j] += 1\n",
    "            l_out[i] += 1\n",
    "            d_graph[j].append(i)\n",
    "            d_graph2[i].add(j)\n",
    "        if max(l_in[1:]) == 1:\n",
    "            l0 = [n for n, x in enumerate(l_out[1:], start=1) if x==0]\n",
    "            while l0:\n",
    "                cur = l0.pop()\n",
    "                for i in d_graph[cur]:\n",
    "                    l_out[i] -= 1\n",
    "                    if l_out[i] == 0:\n",
    "                        l0.append(i)\n",
    "            circle = set(n for n, x in enumerate(l_out[1:], start=1) if x > 0)\n",
    "            for i,j in edges[::-1]:\n",
    "                if i in circle and j in circle:\n",
    "                    return [i, j]            \n",
    "        else:\n",
    "            tar = [n for n, x in enumerate(l_in[1:], start=1) if x==2][0]\n",
    "            root = [n for n, x in enumerate(l_in[1:], start=1) if x==0][0]\n",
    "            def istree(a, b):\n",
    "                d_graph2[a].remove(b)\n",
    "                visited = set()\n",
    "                def visit(node):\n",
    "                    visited.add(node)\n",
    "                    for i in d_graph2[node]:\n",
    "                        if i in visited or not visit(i):\n",
    "                            return False\n",
    "                    return True\n",
    "                if visit(root) and len(visited)==n:\n",
    "                    return True\n",
    "                d_graph2[a].add(b)\n",
    "                return False\n",
    "            for i in d_graph[tar][::-1]:\n",
    "                if istree(i, tar):\n",
    "                    return [i, tar]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def search(self, edges, n):\n",
    "        OD = {}\n",
    "        ID = {}\n",
    "        for e in edges:\n",
    "            OD[e[0]] = OD.get(e[0],[])+[e[1]]\n",
    "            ID[e[1]] = ID.get(e[1],[])+[e[0]]\n",
    "        p=0\n",
    "        s=[edges[0][0]]\n",
    "        while(p<len(s)):\n",
    "            q = s[p]\n",
    "            if len(ID.get(q,[]))>1:\n",
    "                return False\n",
    "            elif len(ID.get(q,[]))==1:\n",
    "                if ID[q][0] not in s:\n",
    "                    s += [ID[q][0]]\n",
    "            for node in OD.get(q,[]):\n",
    "                if node not in s:\n",
    "                    s += [node]\n",
    "            p += 1\n",
    "        if p == n:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "    def findRedundantDirectedConnection(self, edges):\n",
    "        n = len(edges)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if self.search(edges[:i] + edges[i + 1:],n):\n",
    "                return edges[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        ind = {i:0 for i in range(1,n+1)}\n",
    "        adj = {i:[] for i in range(1,n+1)}\n",
    "        for pre,cur in edges:\n",
    "            ind[cur]+=1\n",
    "            adj[pre].append(cur)\n",
    "        root = [i for i in range(1,n+1)if ind[i]==0]\n",
    "        for e in range(n-1,-1,-1):\n",
    "            pre,cur = edges[e]\n",
    "            adj[pre].remove(cur)\n",
    "            ind[cur]-=1\n",
    "            if ind[cur]==0:\n",
    "                root.append(cur)\n",
    "            if len(root)==1:\n",
    "                visited = dict()\n",
    "                def dfs(root):\n",
    "                    if root in visited:\n",
    "                        return\n",
    "                    visited[root]=1\n",
    "                    for n in adj[root]:\n",
    "                        dfs(n)\n",
    "                dfs(root[0])\n",
    "                if len(visited)==n:\n",
    "                    return edges[e]\n",
    "            if cur in root:\n",
    "                root.remove(cur)\n",
    "            ind[cur]+=1\n",
    "            adj[pre].append(cur)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        ind = {i:0 for i in range(1,n+1)}\n",
    "        adj = {i:[] for i in range(1,n+1)}\n",
    "        for pre,cur in edges:\n",
    "            ind[cur]+=1\n",
    "            adj[pre].append(cur)\n",
    "        root = [i for i in range(1,n+1)if ind[i]==0]\n",
    "        for e in edges[::-1]:\n",
    "            pre,cur = e[0],e[1]\n",
    "            adj[pre].remove(cur)\n",
    "            ind[cur]-=1\n",
    "            if ind[cur]==0:\n",
    "                root.append(cur)\n",
    "            if len(root)==1:\n",
    "                visited = dict()\n",
    "                def dfs(root):\n",
    "                    if root in visited:\n",
    "                        return\n",
    "                    visited[root]=1\n",
    "                    for n in adj[root]:\n",
    "                        dfs(n)\n",
    "                dfs(root[0])\n",
    "                if len(visited)==n:\n",
    "                    return e\n",
    "            if cur in root:\n",
    "                root.remove(cur)\n",
    "            ind[cur]+=1\n",
    "            adj[pre].append(cur)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        dct = defaultdict(dict)\n",
    "        in_degree = defaultdict(int)\n",
    "        for i,j in edges:\n",
    "            dct[i][j] = 1\n",
    "            in_degree[j] += 1\n",
    "        n = len(edges)\n",
    "        roots = [i for i in range(1,n+1) if in_degree[i]==0]\n",
    "        for k in range(n-1,-1,-1):\n",
    "            i,j = edges[k]\n",
    "            del dct[i][j]\n",
    "            in_degree[j] -= 1\n",
    "            if in_degree[j] == 0:\n",
    "                roots.append(j)\n",
    "            if len(roots)==1:\n",
    "                visit = defaultdict(int)\n",
    "                def dfs(root):\n",
    "                    if root in visit:\n",
    "                        return \n",
    "                    visit[root] = 1\n",
    "                    for child in dct[root]:\n",
    "                        dfs(child)\n",
    "                    return \n",
    "                dfs(roots[0])\n",
    "                if len(visit) == n:\n",
    "                    return edges[k]    \n",
    "\n",
    "            if j in roots:\n",
    "                roots.remove(j) \n",
    "            dct[i][j] = 1\n",
    "            in_degree[j] += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "from collections import deque\n",
    "from collections import Counter\n",
    "from collections import OrderedDict\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        def get_res_list(res_list, edges, edge_cycle) -> List[int]:\n",
    "            for from_id,to_id in res_list:\n",
    "                if (from_id,to_id) in edge_cycle:\n",
    "                    return [from_id,to_id]\n",
    "            for from_id,to_id in edges[::-1]:\n",
    "                if (from_id,to_id) in edge_cycle:\n",
    "                    return [from_id,to_id]\n",
    "        def get_cycle_edge(vertex_id: int, on_path, edge_cycle) -> None:\n",
    "            beg_ind = False\n",
    "            from_id = 0\n",
    "            for key_id in on_path:\n",
    "                if(not beg_ind):\n",
    "                    if(key_id != vertex_id):\n",
    "                        continue\n",
    "                    else:\n",
    "                        beg_ind = True\n",
    "                        from_id = key_id\n",
    "                else:\n",
    "                    edge_cycle[(from_id,key_id)] = True\n",
    "                    from_id = key_id\n",
    "            \n",
    "            edge_cycle[(from_id,vertex_id)] = True\n",
    "\n",
    "        def traverse(vertex_id: int) -> None:\n",
    "            nonlocal has_cycle\n",
    "            # 必须放在第一位，否则可能成环时候检测不出来\n",
    "            if vertex_id in on_path:\n",
    "                has_cycle = True\n",
    "                get_cycle_edge(vertex_id, on_path, edge_cycle)\n",
    "                return\n",
    "            if visited[vertex_id] or has_cycle:\n",
    "                return\n",
    "\n",
    "            visited[vertex_id] = True\n",
    "            on_path[vertex_id] = True\n",
    "            if(vertex_id in graphs):\n",
    "                for adj_id in graphs[vertex_id]:\n",
    "                    traverse(adj_id)\n",
    "            on_path.pop(vertex_id)\n",
    "\n",
    "        graphs = {}\n",
    "        n = len(edges)\n",
    "        in_degrees = [[] for _ in range(n+1)]\n",
    "        res_list = []\n",
    "        last_res = None\n",
    "        for from_id,to_id in edges:\n",
    "            if(from_id not in graphs):\n",
    "                graphs[from_id] = []\n",
    "            graphs[from_id].append(to_id)\n",
    "            in_degrees[to_id].append(from_id)\n",
    "            \n",
    "            if(len(in_degrees[to_id]) >=2):\n",
    "                res_list = [[src,to_id] for src in in_degrees[to_id]]\n",
    "                last_res = [from_id,to_id]\n",
    "        \n",
    "        visited = [False for _ in range(n+1)]\n",
    "        on_path = OrderedDict()\n",
    "        edge_cycle = {}\n",
    "\n",
    "        has_cycle = False\n",
    "        for head_id in graphs.keys():\n",
    "            if not has_cycle:\n",
    "                traverse(head_id)\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        if(has_cycle):\n",
    "            return get_res_list(res_list,edges,edge_cycle)\n",
    "        else:\n",
    "            return last_res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\r\n",
    "        n = len(edges)\r\n",
    "        graph = [[] for _ in range(n + 1)]\r\n",
    "        d = [0] * (n + 1)\r\n",
    "        for u, v in edges:\r\n",
    "            graph[u].append(v)\r\n",
    "            d[v] += 1\r\n",
    "        root = 0\r\n",
    "        for i in range(1, n + 1):\r\n",
    "            if d[i] == 0:\r\n",
    "                root = i\r\n",
    "                break\r\n",
    "        vis = [0] * (n + 1)\r\n",
    "        def istree(u, idx):\r\n",
    "            if vis[u] > 0:\r\n",
    "                return False\r\n",
    "            vis[u] = 1\r\n",
    "            for v in graph[u]:\r\n",
    "                if u == edges[idx][0] and v == edges[idx][1]:\r\n",
    "                    continue\r\n",
    "                if not istree(v, idx):\r\n",
    "                    return False\r\n",
    "            return True\r\n",
    "        for i in range(len(edges)-1, -1, -1):\r\n",
    "            u, v = edges[i]\r\n",
    "            if d[v] == 1:\r\n",
    "                vis = [0] * (n + 1)\r\n",
    "                if istree(v, i) and sum(vis) == n:\r\n",
    "                    return [u, v]\r\n",
    "            else:\r\n",
    "                vis = [0] * (n + 1)\r\n",
    "                if istree(root, i) and sum(vis) == n:\r\n",
    "                    return [u, v]\r\n",
    "        return []\r\n",
    "\r\n",
    "\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "\n",
    "        # 记录图的边关系\n",
    "        dct = defaultdict(dict)\n",
    "        in_degree = defaultdict(int)\n",
    "        for i, j in edges:\n",
    "            dct[i][j] = 1\n",
    "            in_degree[j] += 1\n",
    "\n",
    "        # 倒序枚举\n",
    "        n = len(edges)\n",
    "        roots = [i for i in range(1, n + 1) if in_degree[i] == 0]\n",
    "        for k in range(n - 1, -1, -1):\n",
    "            i, j = edges[k]\n",
    "            del dct[i][j]\n",
    "            in_degree[j] -= 1\n",
    "            if in_degree[j] == 0:\n",
    "                roots.append(j)\n",
    "\n",
    "            # 当只有一个根的时候进行检查\n",
    "            if len(roots) == 1:\n",
    "                visit = defaultdict(int)\n",
    "\n",
    "                def dfs(root):\n",
    "                    if root in visit:\n",
    "                        return\n",
    "                    visit[root] = 1\n",
    "                    for child in dct[root]:\n",
    "                        dfs(child)\n",
    "                    return\n",
    "\n",
    "                dfs(roots[0])\n",
    "                if len(visit) == n:\n",
    "                    return edges[k]\n",
    "\n",
    "                    # 恢复原状\n",
    "            if j in roots:\n",
    "                roots.remove(j)\n",
    "            dct[i][j] = 1\n",
    "            in_degree[j] += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Unionfind:\n",
    "    def __init__(self, n):\n",
    "        self.parent = [x for x in range(n)]\n",
    "        self.size = [1 for _ in range(n)]\n",
    "    def getGroup(self, n):\n",
    "        while self.parent[n] != n:\n",
    "            n = self.parent[n]\n",
    "        return n\n",
    "    def isParent(self, n, target):\n",
    "        while self.parent[n] != n:\n",
    "            if self.parent[n] == target:\n",
    "                return True\n",
    "            n = self.parent[n]\n",
    "        return False\n",
    "    def union(self, n1, n2):\n",
    "        self.parent[n2] = n1\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = max(max(x) for x in edges)\n",
    "        indegree = [0 for _ in range(n)]\n",
    "        outdegree = [0 for _ in range(n)]\n",
    "        children = [[] for _ in range(n)]\n",
    "        edgeIndexMap = {}\n",
    "        uf = Unionfind(n)\n",
    "        for i, edge in enumerate(edges):\n",
    "            e1, e2 = edge[0]-1, edge[1]-1\n",
    "            indegree[e2]+=1\n",
    "            outdegree[e1]+=1\n",
    "            children[e1].append(e2)\n",
    "            edgeIndexMap[(e1, e2)] = i\n",
    "        for startNode in range(n):\n",
    "            if indegree[startNode] == 0:\n",
    "                dq = collections.deque()\n",
    "                dq.append(startNode)\n",
    "                visited = {startNode:0}\n",
    "                print(startNode)\n",
    "                while dq:\n",
    "                    curNode = dq.popleft()\n",
    "                    for child in children[curNode]:\n",
    "                        if child not in visited.keys():\n",
    "                            visited[child] = curNode\n",
    "                            dq.append(child)\n",
    "                            uf.union(curNode, child)\n",
    "                        else:\n",
    "                            # print((visited[child], child))\n",
    "                            if edgeIndexMap[(visited[child], child)] > edgeIndexMap[(curNode, child)] and not uf.isParent(curNode, child):\n",
    "                                return [visited[child]+1, child+1]\n",
    "                            else:\n",
    "                                return [curNode+1, child+1]\n",
    "        \n",
    "        print(1)\n",
    "        for edge in edges:\n",
    "            e1, e2 = edge[0]-1, edge[1]-1\n",
    "            if uf.getGroup(e1) == uf.getGroup(e2):\n",
    "                return [e1+1, e2+1]\n",
    "            uf.union(e1, e2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "\n",
    "        # 记录图的边关系\n",
    "        dct = defaultdict(dict)\n",
    "        in_degree = defaultdict(int)\n",
    "        for i, j in edges:\n",
    "            dct[i][j] = 1\n",
    "            in_degree[j] += 1\n",
    "\n",
    "        # 倒序枚举\n",
    "        n = len(edges)\n",
    "        roots = [i for i in range(1, n+1) if in_degree[i]==0]\n",
    "        for k in range(n-1, -1, -1):\n",
    "            i, j = edges[k]\n",
    "            del dct[i][j]\n",
    "            in_degree[j] -= 1\n",
    "            if in_degree[j] == 0:\n",
    "                roots.append(j)\n",
    "            \n",
    "            # 当只有一个根的时候进行检查\n",
    "            if len(roots) == 1:\n",
    "                visit = defaultdict(int)\n",
    "                def dfs(root):\n",
    "                    if root in visit:\n",
    "                        return \n",
    "                    visit[root] = 1\n",
    "                    for child in dct[root]:\n",
    "                        dfs(child)\n",
    "                    return \n",
    "                dfs(roots[0])\n",
    "                if len(visit) == n:\n",
    "                    return edges[k]    \n",
    "\n",
    "            # 恢复原状\n",
    "            if j in roots:\n",
    "                roots.remove(j) \n",
    "            dct[i][j] = 1\n",
    "            in_degree[j] += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        def find(i):\n",
    "            if fa[i] == i:\n",
    "                return i\n",
    "            else:\n",
    "                fa[i] = find(fa[i])\n",
    "                return fa[i]\n",
    "        def join(i, j):\n",
    "            u = find(i)\n",
    "            v = find(j)\n",
    "            if u != v:\n",
    "                fa[v] = u\n",
    "                return None\n",
    "            if u == v:\n",
    "                return [i, j]\n",
    "        # in-degree == 2\n",
    "        import collections\n",
    "        indegree_dict = collections.defaultdict(int)\n",
    "        for i, j in edges:\n",
    "            indegree_dict[j] += 1\n",
    "        fa = [i for i in range(0, 1001)]\n",
    "        cands = []\n",
    "        result = None\n",
    "        for i, j in edges:\n",
    "            if indegree_dict[j] == 2:\n",
    "                cands.append([i,j])\n",
    "            else:\n",
    "                tmpresult = join(i, j)\n",
    "                result = tmpresult if tmpresult is not None else result\n",
    "        if not cands:\n",
    "            return result\n",
    "        else:\n",
    "            if find(cands[1][0]) == find(cands[1][1]): # must rm the second one\n",
    "                return cands[1]\n",
    "            elif find(cands[0][0]) == find(cands[0][1]): # must rm the first one\n",
    "                return cands[0]\n",
    "            else: # both will be ok\n",
    "                return cands[1]\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        parent = list(range(1001))\n",
    "        def find(x):\n",
    "            if x != parent[x]:\n",
    "                parent[x] = find(parent[x])\n",
    "            return parent[x]\n",
    "        def union(x, y):\n",
    "            root1, root2 = find(x), find(y)\n",
    "            parent[root1] = root2\n",
    "        def check(remove):\n",
    "            for u, v in edges:\n",
    "                if u == remove[0] and v == remove[1]:\n",
    "                    continue\n",
    "                if find(u) == find(v):\n",
    "                    return False\n",
    "                else:\n",
    "                    union(u, v)\n",
    "            return True\n",
    "\n",
    "        n = len(edges)\n",
    "        deg = [0] * (n + 1)\n",
    "        ans = []\n",
    "        for u, v in edges:\n",
    "            deg[v] += 1\n",
    "            if deg[v] == 2:\n",
    "                if check([u, v]):\n",
    "                    return [u, v]\n",
    "                else:\n",
    "                    for uu, vv in edges:\n",
    "                        if vv == v:\n",
    "                            return [uu, vv]\n",
    "        \n",
    "        parent = list(range(1001))\n",
    "        for u, v in edges:\n",
    "            if find(u) == find(v):\n",
    "                return [u, v]\n",
    "            union(u, v)\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: list[list[int]]) -> list[int]:\n",
    "        n = len(edges)\n",
    "        res = None\n",
    "        adjhash = defaultdict(set)\n",
    "        invadjhash = defaultdict(set)\n",
    "        for i, j in edges:\n",
    "            adjhash[i].add(j)\n",
    "            invadjhash[j].add(i)\n",
    "        edges = edges[::-1]\n",
    "\n",
    "        for l, m in edges:\n",
    "            if res:\n",
    "                return res\n",
    "            adjhash[l].remove(m)\n",
    "            invadjhash[m].remove(l)\n",
    "            rootCount = 0\n",
    "            root = None\n",
    "            for r in range(1, n + 1):\n",
    "                if not invadjhash[r] and adjhash[r]:\n",
    "                    rootCount += 1\n",
    "                    root = r\n",
    "            if rootCount == 1:\n",
    "                visited = set()\n",
    "                que = deque()\n",
    "                que += ([root])\n",
    "                while que:\n",
    "                    for _ in range(len(que)):\n",
    "                        now = que.popleft()\n",
    "                        if now in visited:\n",
    "                            continue\n",
    "                        visited.add(now)\n",
    "                        for neiber in adjhash[now]:\n",
    "                            que.append(neiber)\n",
    "                if len(visited) == n:\n",
    "                    res = [l, m]\n",
    "            adjhash[l].add(m)\n",
    "            invadjhash[m].add(l)\n",
    "        return res\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    obj = Solution()\n",
    "    edges = [[1, 2], [2, 3], [3, 4], [4, 1], [1, 5]]\n",
    "    print(obj.findRedundantDirectedConnection(edges))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "思路：并查集-分两种情况，第1种是存在入度为2的节点（要删除的就是指向该节点的两条边之一），第2种是存在环\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        p = list(range(1001))\n",
    "        def find(x):\n",
    "            if p[x] == x:\n",
    "                return p[x]\n",
    "            p[x] = find(p[x])\n",
    "            return p[x]\n",
    "        \n",
    "        def is_same(u, v):\n",
    "            u = find(u)\n",
    "            v = find(v)\n",
    "            return u == v\n",
    "\n",
    "        def join(u, v):\n",
    "            u = find(u)\n",
    "            v = find(v)\n",
    "            if u == v: return\n",
    "            p[v] = u\n",
    "        \n",
    "        in_degree = [0] * 1001\n",
    "        for u, v in edges:\n",
    "            in_degree[v] += 1\n",
    "        \n",
    "        def get_remove_edge(edges):\n",
    "            for u, v in edges:\n",
    "                if is_same(u, v):\n",
    "                    return [u,v]\n",
    "                join(u, v)\n",
    "        \n",
    "        def tree_after_remove(edges, e):\n",
    "            for u, v in edges:\n",
    "                if (u, v) == tuple(e):\n",
    "                    continue\n",
    "                if is_same(u, v):\n",
    "                    return False\n",
    "                join(u, v)\n",
    "            return True\n",
    "        candidates = []\n",
    "        for e in edges[::-1]:\n",
    "            if in_degree[e[1]] == 2:\n",
    "                candidates.append(e)\n",
    "        \n",
    "        if candidates:\n",
    "            if tree_after_remove(edges, candidates[0]):\n",
    "                return candidates[0]\n",
    "            else: return candidates[1]\n",
    "        \n",
    "        return get_remove_edge(edges)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        # relationship dict between node and edge\n",
    "        dct = collections.defaultdict(dict)\n",
    "        in_degree = collections.defaultdict(int)\n",
    "        for i, j in edges:\n",
    "            dct[i][j] = 1\n",
    "            in_degree[j] += 1\n",
    "        # print(dct)\n",
    "        # print(in_degree)\n",
    "        # iterate in reverse order\n",
    "        n = len(edges)\n",
    "        roots = [i for i in range(1, n+1) if in_degree[i]==0]\n",
    "        print(roots)\n",
    "        for k in range(n-1, -1, -1):\n",
    "            i, j = edges[k]\n",
    "            del dct[i][j]\n",
    "            in_degree[j] -= 1\n",
    "            if in_degree[j] == 0:\n",
    "                roots.append(j)\n",
    "            \n",
    "            # check when there is only one root\n",
    "            if len(roots) == 1:\n",
    "                visit = collections.defaultdict(int)\n",
    "                def dfs(root):\n",
    "                    if root in visit:\n",
    "                        return\n",
    "                    visit[root] = 1\n",
    "                    for child in dct[root]:\n",
    "                        dfs(child)\n",
    "                    return\n",
    "                dfs(roots[0])\n",
    "                if len(visit) == n:\n",
    "                    return edges[k]\n",
    "            \n",
    "            # return to the original\n",
    "            if j in roots:\n",
    "                roots.remove(j)\n",
    "            dct[i][j] = 1\n",
    "            in_degree[j] += 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n=1005\n",
    "        fa=[i for i in range(n)]\n",
    "        for i in range(n):\n",
    "            fa[i]=i\n",
    "        def find(u):\n",
    "            if u!=fa[u]:\n",
    "                fa[u]=find(fa[u])\n",
    "            return fa[u]\n",
    "        def join(u,v):\n",
    "            u=find(u)\n",
    "            v=find(v)\n",
    "            if u!=v:\n",
    "                fa[v]=u\n",
    "        def getRemove(edges):\n",
    "            for i,j in edges:\n",
    "                if find(i)==find(j):\n",
    "                    return [i,j]\n",
    "                else:\n",
    "                    join(i,j)\n",
    "            return []\n",
    "        def isTree(edges,delete):\n",
    "            for i,j in edges:\n",
    "                if [i,j] == delete:\n",
    "                    continue\n",
    "                if find(i)==find(j):\n",
    "                    return False\n",
    "                join(i,j)\n",
    "            return True\n",
    "        inDegree=[0 for i in range(n)]\n",
    "        for i in range(len(edges)):\n",
    "            inDegree[edges[i][1]]+=1  \n",
    "        twoDegree=[]\n",
    "        for i in range(len(edges)-1,-1,-1):\n",
    "            if inDegree[edges[i][1]]==2:\n",
    "                twoDegree.append(edges[i])\n",
    "        if len(twoDegree)>0:\n",
    "            if isTree(edges,twoDegree[0]):\n",
    "                return twoDegree[0]\n",
    "            return twoDegree[1]\n",
    "        return getRemove(edges)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class UF:\n",
    "#     def __init__(self, n):\n",
    "#         self.n = n\n",
    "#         self.size = [1] * n\n",
    "#         self.parent = list(range(n))\n",
    "    \n",
    "#     def find(self, x):\n",
    "#         if self.parent[x] != x:\n",
    "#             self.parent[x] = self.find(self.parent[x])\n",
    "#         return self.parent[x]\n",
    "    \n",
    "#     def connect(self, x, y):\n",
    "#         rx, ry = self.find(x), self.find(y)\n",
    "#         return rx == ry\n",
    "    \n",
    "#     # 使得y的祖先更改为x\n",
    "#     def union(self, x, y):\n",
    "#         rx, ry = self.find(x), self.find(y)\n",
    "#         if rx == ry:\n",
    "#             return\n",
    "#         self.parent[ry] = rx\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        graph = defaultdict(set)\n",
    "        # 入度\n",
    "        ind = defaultdict(int)\n",
    "        for a, b in edges:\n",
    "            graph[a].add(b)\n",
    "            ind[b] += 1\n",
    "\n",
    "        pool = set()\n",
    "        for i in range(1,n+1):\n",
    "            if ind[i] == 0:  \n",
    "                pool.add(i)\n",
    "\n",
    "        \n",
    "        def dfs(u):\n",
    "            vis[u] = 1\n",
    "            for v in graph[u]:\n",
    "                if vis[v] == 0:\n",
    "                    dfs(v)\n",
    "                else:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        for a, b in edges[::-1]:\n",
    "            graph[a].remove(b)\n",
    "            ind[b] -= 1\n",
    "            if ind[b] == 0:\n",
    "                pool.add(b)\n",
    "            for u in pool:\n",
    "                vis = [0]*(n+1) \n",
    "                flag = dfs(u)\n",
    "                # print(u, flag, vis)\n",
    "                if flag and sum(vis) == n:\n",
    "                    return [a,b]\n",
    "            graph[a].add(b)\n",
    "            if ind[b] == 0:\n",
    "                pool.remove(b)\n",
    "            ind[b] += 1\n",
    "            \n",
    "\n",
    "        \n",
    "        return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = 1005\n",
    "        fa = [0] * n\n",
    "\n",
    "        def find(i):\n",
    "            if fa[i] == i:\n",
    "                return i\n",
    "            else:\n",
    "                fa[i] = find(fa[i])\n",
    "                return fa[i]\n",
    "            \n",
    "        def union(i, j):\n",
    "            fi = find(i)\n",
    "            fj = find(j)\n",
    "            fa[fj] = fi\n",
    "\n",
    "        def removeFromTwo(edges, idx):\n",
    "            for i in range(n):\n",
    "                fa[i] = i\n",
    "\n",
    "            for i in range(len(edges)):\n",
    "                if i == idx:\n",
    "                    continue\n",
    "                if find(edges[i][0]) == find(edges[i][1]):\n",
    "                    return False\n",
    "                union(edges[i][0], edges[i][1])\n",
    "\n",
    "            return True\n",
    "        \n",
    "        def removeFromCircle(edges):\n",
    "            for i in range(n):\n",
    "                fa[i] = i\n",
    "\n",
    "            for i in range(len(edges)):\n",
    "                if find(edges[i][0]) == find(edges[i][1]):\n",
    "                    return edges[i]\n",
    "                union(edges[i][0], edges[i][1])\n",
    "                \n",
    "\n",
    "        inDegree = [0] * n\n",
    "        for edge in edges:\n",
    "            inDegree[edge[1]] += 1\n",
    "\n",
    "        twoDegree = []\n",
    "        for i in range(len(edges))[::-1]:\n",
    "            if inDegree[edges[i][1]] == 2:\n",
    "                twoDegree.append(i)\n",
    "\n",
    "        if twoDegree:\n",
    "            if removeFromTwo(edges, twoDegree[0]):\n",
    "                return edges[twoDegree[0]]\n",
    "            else:\n",
    "                return edges[twoDegree[1]]\n",
    "            \n",
    "        return removeFromCircle(edges)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        self.father = [i for i in range(1010)]\n",
    "        def find(u):\n",
    "            if self.father[u] == u:\n",
    "                return self.father[u]\n",
    "            self.father[u] = find(self.father[u])\n",
    "            return self.father[u]\n",
    "        \n",
    "        def isSame(u, v):\n",
    "            u = find(u)\n",
    "            v = find(v)\n",
    "            return u == v\n",
    "        \n",
    "        def join(u, v):\n",
    "            u = find(u)\n",
    "            v = find(v)\n",
    "            if u == v:\n",
    "                return\n",
    "            self.father[v] = u\n",
    "\n",
    "        def isTreeAfterRemoveEdge(edges, index):\n",
    "            for i in range(len(edges)):\n",
    "                if i == index:\n",
    "                    continue\n",
    "                if isSame(edges[i][0], edges[i][1]):\n",
    "                    return False\n",
    "                join(edges[i][0], edges[i][1])\n",
    "            return True\n",
    "        \n",
    "        inDegree = [0 for _ in range(1010)]\n",
    "        twoDegree = []\n",
    "\n",
    "\n",
    "        for edge in edges:\n",
    "            inDegree[edge[1]] += 1\n",
    "                \n",
    "        for i in range(len(edges)):\n",
    "            if inDegree[edges[i][1]] == 2:\n",
    "                twoDegree.append(i)\n",
    "\n",
    "        if twoDegree:\n",
    "            if isTreeAfterRemoveEdge(edges, twoDegree[-1]):\n",
    "                return edges[twoDegree[-1]]\n",
    "            return edges[twoDegree[0]]\n",
    "        \n",
    "        def getRemoveEdge(edges):\n",
    "            for edge in edges:\n",
    "                if isSame(edge[0], edge[1]):\n",
    "                    return edge\n",
    "                join(edge[0], edge[1])\n",
    "            return []\n",
    "        return getRemoveEdge(edges)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: list[list[int]]) -> list[int]:\n",
    "        n = len(edges)\n",
    "        res = None\n",
    "        adjhash = defaultdict(set)\n",
    "        invadjhash = defaultdict(set)\n",
    "        for i, j in edges:\n",
    "            adjhash[i].add(j)\n",
    "            invadjhash[j].add(i)\n",
    "        print(adjhash)\n",
    "        print(invadjhash)\n",
    "        edges = edges[::-1]\n",
    "\n",
    "        for l, m in edges:\n",
    "            if res:\n",
    "                return res\n",
    "            adjhash[l].remove(m)\n",
    "            invadjhash[m].remove(l)\n",
    "            rootCount = 0\n",
    "            root = None\n",
    "            for r in range(1, n + 1):\n",
    "                if not invadjhash[r] and adjhash[r]:\n",
    "                    rootCount += 1\n",
    "                    root = r\n",
    "            if rootCount == 1:\n",
    "                visited = set()\n",
    "                que = deque()\n",
    "                que += ([root])\n",
    "                while que:\n",
    "                    for _ in range(len(que)):\n",
    "                        now = que.popleft()\n",
    "                        if now in visited:\n",
    "                            continue\n",
    "                        visited.add(now)\n",
    "                        for neiber in adjhash[now]:\n",
    "                            que.append(neiber)\n",
    "                if len(visited) == n:\n",
    "                    res = [l, m]\n",
    "            adjhash[l].add(m)\n",
    "            invadjhash[m].add(l)\n",
    "        return res\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    obj = Solution()\n",
    "    edges = [[1, 2], [2, 3], [3, 4], [4, 1], [1, 5]]\n",
    "    print(obj.findRedundantDirectedConnection(edges))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        dic = defaultdict(dict)\n",
    "        in_dgree = defaultdict(int)\n",
    "        for i, j in edges:\n",
    "            dic[i][j] = 1 #节点链接关系\n",
    "            in_dgree[j] += 1 # 每个节点的入度\n",
    "        \n",
    "        n = len(edges)\n",
    "        roots = [i for i in range(1, n+1) if in_dgree[i]==0] # 入度为0 即根节点\n",
    "        for k in range(n-1, -1, -1): # 倒序\n",
    "            i, j = edges[k]\n",
    "            del dic[i][j]  # 找到该节点后删去节点\n",
    "            in_dgree[j] -= 1  # 对应入度-1\n",
    "            if in_dgree[j] == 0: # 若删去后入度为0，则变为根节点\n",
    "                roots.append(j)\n",
    "\n",
    "            if len(roots) == 1:  # 若只有一个根节点\n",
    "                vis = defaultdict(int)  # 记录每个节点是否都能到达\n",
    "                def dfs(root):  # 深度搜索根节点\n",
    "                    if root in vis: # 到达过则退出本次搜索\n",
    "                        return\n",
    "                    vis[root] = 1 # 没有到达过，记录1次\n",
    "                    for child in dic[root]: # 对每个根节点的子节点进行搜索\n",
    "                        dfs(child)\n",
    "                    return\n",
    "                dfs(roots[0])\n",
    "                if len(vis) == n: # 如果所有节点都到达了，则证明找到了可删去的节点\n",
    "                    return edges[k]\n",
    "            if j in roots: # 找了一圈没有，则说明j不适合，从备选中删去\n",
    "                roots.remove(j)\n",
    "            dic[i][j] = 1 # 恢复删去的节点\n",
    "            in_dgree[j] += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.father=[0 for _ in range(1001)]\n",
    "\n",
    "\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        def init():\n",
    "            for i in range(len(self.father)):\n",
    "                self.father[i]=i\n",
    "        \n",
    "        def find(u):\n",
    "            if u==self.father[u]:\n",
    "                return u\n",
    "            return find(self.father[u])\n",
    "        def isSame(u,v):\n",
    "            u=find(u)\n",
    "            v=find(v)\n",
    "            return u==v\n",
    "        def join(u,v):\n",
    "            u=find(u)\n",
    "            v=find(v)\n",
    "            if u==v:\n",
    "                return\n",
    "            self.father[v]=u\n",
    "        def isTreeAfterRemove(edges,index):\n",
    "            init()\n",
    "            for i in range(len(edges)):\n",
    "                #模拟删除入度为2的节点\n",
    "                if i==index:\n",
    "                    continue\n",
    "                if isSame(edges[i][0],edges[i][1]):\n",
    "                    return False\n",
    "                join(edges[i][0],edges[i][1])\n",
    "            return True\n",
    "\n",
    "        indegreed=[0 for _ in range(1001)]\n",
    "        for e in edges:\n",
    "            indegreed[e[1]]+=1\n",
    "        \n",
    "        nodes=[]\n",
    "        for i in range(len(edges)):\n",
    "            if indegreed[edges[i][1]]==2:\n",
    "                nodes.append(i)\n",
    "        print(nodes)\n",
    "        if len(nodes)==2:\n",
    "            if isTreeAfterRemove(edges,nodes[1]):\n",
    "                return edges[nodes[1]]\n",
    "            # if isTreeAfterRemove(edges,nodes[0]):\n",
    "            else:\n",
    "                return edges[nodes[0]]\n",
    "        print(\"888888888888888888888888888888888888888\")\n",
    "        #记录入度为2的节点：\n",
    "        result=[]\n",
    "        init()\n",
    "        for e in edges:\n",
    "            if isSame(e[0],e[1]):\n",
    "                return [e[0],e[1]]\n",
    "            join(e[0],e[1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.father=[0 for _ in range(1001)]\n",
    "\n",
    "\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        def init():\n",
    "            for i in range(len(self.father)):\n",
    "                self.father[i]=i\n",
    "        \n",
    "        def find(u):\n",
    "            if u==self.father[u]:\n",
    "                return u\n",
    "            return find(self.father[u])\n",
    "        def isSame(u,v):\n",
    "            u=find(u)\n",
    "            v=find(v)\n",
    "            return u==v\n",
    "        def join(u,v):\n",
    "            u=find(u)\n",
    "            v=find(v)\n",
    "            if u==v:\n",
    "                return\n",
    "            self.father[v]=u\n",
    "        def isTreeAfterRemove(edges,index):\n",
    "            init()\n",
    "            for i in range(len(edges)):\n",
    "                #模拟删除入度为2的节点\n",
    "                if i==index:\n",
    "                    continue\n",
    "                if isSame(edges[i][0],edges[i][1]):\n",
    "                    return False\n",
    "                join(edges[i][0],edges[i][1])\n",
    "            return True\n",
    "\n",
    "        indegreed=[0 for _ in range(1001)]\n",
    "        for e in edges:\n",
    "            indegreed[e[1]]+=1\n",
    "        \n",
    "        nodes=[]\n",
    "        for i in range(len(edges)):\n",
    "            if indegreed[edges[i][1]]==2:\n",
    "                nodes.append(i)\n",
    "        print(nodes)\n",
    "        if len(nodes)==2:\n",
    "            if isTreeAfterRemove(edges,nodes[1]):\n",
    "                return edges[nodes[1]]\n",
    "            # if isTreeAfterRemove(edges,nodes[0]):\n",
    "            else:\n",
    "                return edges[nodes[0]]\n",
    "        #记录入度为2的节点：\n",
    "        result=[]\n",
    "        init()\n",
    "        for e in edges:\n",
    "            if isSame(e[0],e[1]):\n",
    "                return [e[0],e[1]]\n",
    "            join(e[0],e[1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        father = [i for i in range(1005)]\n",
    "        def find(a):\n",
    "            if a == father[a]:\n",
    "                return a\n",
    "            else:\n",
    "                father[a] = find(father[a])\n",
    "                return father[a] \n",
    "\n",
    "        def join(a,b):\n",
    "            a = find(a)\n",
    "            b = find(b)\n",
    "            if a == b:\n",
    "                return \n",
    "            else:\n",
    "                father[a] = b\n",
    "\n",
    "        def issame(a,b):\n",
    "            a = find(a)\n",
    "            b = find(b)\n",
    "            return a == b\n",
    "\n",
    "        def entertwo(a): # 多的那个路径是指向树中的节点\n",
    "            father = [i for i in range(100)]\n",
    "            for i in range(len(edges)):\n",
    "                if edges[i][0] == a:continue\n",
    "                if issame(edges[i][0],edges[i][1]):\n",
    "                    return False # 如果屏蔽了a，其余的还是有重复，就说明应该删除另一个\n",
    "                join(edges[i][0],edges[i][1])\n",
    "            return True # 如果屏蔽了a,其余的可以组成一个树，就说明a是多余的\n",
    "\n",
    "        def outtwo(): # 多的那个路径是被树中的路径指向\n",
    "            father = [i for i in range(100)]\n",
    "            for i in range(len(edges)):\n",
    "                if issame(edges[i][0],edges[i][1]):\n",
    "                    return edges[i]\n",
    "                else:\n",
    "                    join(edges[i][0],edges[i][1])\n",
    "\n",
    "        enter = {}\n",
    "        twoD = [] # 保存的是指向的是入度为2的节点的起始节点\n",
    "        twoend = 0 # 用以保存入度为2的节点\n",
    "        for i in range(len(edges)):\n",
    "            enter[edges[i][1]] = enter.get(edges[i][1],0) + 1\n",
    "        for k,v in enter.items():\n",
    "            if v == 2:\n",
    "                for i,j in edges:\n",
    "                    if j == k:\n",
    "                        twoD.append(i)\n",
    "                        twoend = k\n",
    "        print(twoD)\n",
    "        if twoD:#如果有入度为2的情况，则一定是有两条边，一定是删除入度为2的两条边的其中一条\n",
    "            if entertwo(twoD[1]):\n",
    "                return [twoD[1],twoend]\n",
    "            else:\n",
    "                return [twoD[0],twoend]\n",
    "        return outtwo()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        g = defaultdict(list) \n",
    "        n = len(edges)\n",
    "        indeg = [0] * (n+1)\n",
    "        for i, (a, b) in enumerate(edges):\n",
    "            g[a].append((i, b))\n",
    "            #g[b].append((i, a)) \n",
    "            indeg[b] += 1\n",
    "        root = -1 \n",
    "        x = -1 \n",
    "        for i in range(1, n+1):\n",
    "            if indeg[i] == 0:\n",
    "                root = i \n",
    "            elif indeg[i] == 2:\n",
    "                x = i \n",
    "        circle = [0] * (n+1) \n",
    "        vis = [0] * (n+1) \n",
    "        \n",
    "        def dfs(x, fa):\n",
    "            vis[x] = 1\n",
    "            for i, y in g[x]:\n",
    "                if not vis[y]:\n",
    "                    if dfs(y, x):\n",
    "                        circle[x] = 1\n",
    "                        return True \n",
    "                else:\n",
    "                    circle[x] = 1\n",
    "                    return True \n",
    "            return False \n",
    "        if root == -1:\n",
    "            for i in range(1, n+1):\n",
    "                if not vis[i]:\n",
    "                    dfs(i, i) \n",
    "            for (a, b) in edges[::-1]:\n",
    "                if circle[a] == circle[b] == 1:\n",
    "                    return [a, b] \n",
    "        flag = 0 # c, f \n",
    "        fa = -1 \n",
    "        Q = deque() \n",
    "        for i, y in g[x]:\n",
    "            Q.append((y, x))\n",
    "        while Q:\n",
    "            u, pre= Q.popleft() \n",
    "            if u == x:\n",
    "                flag = 1 # b \n",
    "                fa = pre\n",
    "                break \n",
    "            for i,v in g[u]:\n",
    "                Q.append((v, u)) \n",
    "        if flag == 1:\n",
    "            return [pre, x] \n",
    "        else:\n",
    "            for [a, b] in edges[::-1]:\n",
    "                if b == x:\n",
    "                    return [a ,b]\n",
    "        \n",
    "\n",
    "\n",
    "        \n",
    "         \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "         \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        father = [i for i in range(1005)]\n",
    "        def find(a):\n",
    "            if a == father[a]:\n",
    "                return a\n",
    "            else:\n",
    "                father[a] = find(father[a])\n",
    "                return father[a] \n",
    "\n",
    "        def join(a,b):\n",
    "            a = find(a)\n",
    "            b = find(b)\n",
    "            if a == b:\n",
    "                return \n",
    "            else:\n",
    "                father[a] = b\n",
    "\n",
    "        def issame(a,b):\n",
    "            a = find(a)\n",
    "            b = find(b)\n",
    "            return a == b\n",
    "\n",
    "        def entertwo(a): # 多的那个路径是指向树中的节点\n",
    "            father = [i for i in range(100)]\n",
    "            for i in range(len(edges)):\n",
    "                if edges[i][0] == a:continue\n",
    "                if issame(edges[i][0],edges[i][1]):\n",
    "                    return False # 如果屏蔽了a，其余的还是有重复，就说明应该删除另一个\n",
    "                join(edges[i][0],edges[i][1])\n",
    "            return True # 如果屏蔽了a,其余的可以组成一个树，就说明a是多余的\n",
    "\n",
    "        def outtwo(): # 多的那个路径是被树中的路径指向\n",
    "            father = [i for i in range(100)]\n",
    "            for i in range(len(edges)):\n",
    "                if issame(edges[i][0],edges[i][1]):\n",
    "                    return edges[i]\n",
    "                else:\n",
    "                    join(edges[i][0],edges[i][1])\n",
    "\n",
    "        enter = {}\n",
    "        twoD = [] # 保存的是指向的是入度为2的节点的起始节点\n",
    "        twoend = 0 # 用以保存入度为2的节点\n",
    "        for i in range(len(edges)):\n",
    "            enter[edges[i][1]] = enter.get(edges[i][1],0) + 1\n",
    "        for k,v in enter.items():\n",
    "            if v == 2:\n",
    "                for i,j in edges:\n",
    "                    if j == k:\n",
    "                        twoD.append(i)\n",
    "                        twoend = k\n",
    "        if twoD:#如果有入度为2的情况，则一定是有两条边，一定是删除入度为2的两条边的其中一条\n",
    "            if entertwo(twoD[1]):\n",
    "                return [twoD[1],twoend]\n",
    "            else:\n",
    "                return [twoD[0],twoend]\n",
    "        return outtwo()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        father = [i for i in range(n + 1)]\n",
    "        circle_edge = None\n",
    "        conflict_edge_a = None\n",
    "        conflict_edge_b = None\n",
    "\n",
    "        def find(x):\n",
    "            root = x\n",
    "            if x != father[x]:\n",
    "                root = find(father[x])\n",
    "            return root\n",
    "\n",
    "        for u, v in edges:\n",
    "            if find(u) == find(v):\n",
    "                circle_edge = [u, v]\n",
    "\n",
    "            elif father[v] == v:\n",
    "                father[v] = u\n",
    "\n",
    "            else:\n",
    "                conflict_edge_a = [u, v]\n",
    "                conflict_edge_b = [father[v], v]\n",
    "\n",
    "        if conflict_edge_a == None:\n",
    "            return circle_edge\n",
    "        elif circle_edge == None:\n",
    "            return conflict_edge_a\n",
    "        else:\n",
    "            return conflict_edge_b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = 1001\n",
    "        p = [i for i in range(n)]\n",
    "        def find(x):\n",
    "            if p[x] != x:\n",
    "                p[x] = find(p[x])\n",
    "            return p[x]\n",
    "        def join(u, v):\n",
    "            u = find(u)\n",
    "            v = find(v)\n",
    "            if u == v:\n",
    "                return\n",
    "            p[v] = u\n",
    "\n",
    "        def same(u, v):\n",
    "            u = find(u)\n",
    "            v = find(v)\n",
    "            return u == v\n",
    "        def getremove(edges):\n",
    "            for i in range(len(edges)):\n",
    "                if same(edges[i][0], edges[i][1]):\n",
    "                    return edges[i]\n",
    "                else:\n",
    "                    join(edges[i][0], edges[i][1])\n",
    "            return []\n",
    "        \n",
    "        def istreevalid(edges, deleedge):\n",
    "            for i in range(len(edges)):\n",
    "                if i == deleedge:\n",
    "                    continue\n",
    "                if same(edges[i][0], edges[i][1]):\n",
    "                    return False\n",
    "                else:\n",
    "                    join(edges[i][0], edges[i][1])\n",
    "            return True\n",
    "        indegree = [0] * n\n",
    "        for i in range(len(edges)):\n",
    "            indegree[edges[i][1]] += 1\n",
    "        twoindegree = []\n",
    "        for i in range(len(edges))[::-1]:\n",
    "            if indegree[edges[i][1]] == 2:\n",
    "                twoindegree.append(i)\n",
    "        if len(twoindegree) > 0:\n",
    "            if istreevalid(edges, twoindegree[0]):\n",
    "                return edges[twoindegree[0]]\n",
    "            return edges[twoindegree[1]]\n",
    "        return getremove(edges)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self) -> None:\n",
    "        self.father = [i for i in range(1005)]\n",
    "        \n",
    "    def init_father(self):\n",
    "        self.father = [i for i in range(1005)]\n",
    "    \n",
    "    def find(self, a):\n",
    "        return a if self.father[a] == a else self.find(self.father[a])\n",
    "    \n",
    "    def add(self, a, b):\n",
    "        self.father[b] = a\n",
    "    \n",
    "    def istree_afterremove(self, edges, u, v):\n",
    "        self.init_father()\n",
    "        for edge in edges:\n",
    "            if edge[0] == u and edge[1] == v:\n",
    "                continue\n",
    "            fu = self.find(edge[0])\n",
    "            fv = self.find(edge[1])\n",
    "            if fu == fv:\n",
    "                # 已经有环，退出\n",
    "                return False\n",
    "            self.add(edge[0], edge[1])\n",
    "        return True\n",
    "    \n",
    "    def find_remove_edge(self, edges):\n",
    "        self.init_father()\n",
    "        for edge in edges:\n",
    "            fv = self.find(edge[0])\n",
    "            fu = self.find(edge[1])\n",
    "            if fv == fu:\n",
    "                return [edge[0], edge[1]]\n",
    "            self.add(edge[0], edge[1])\n",
    "            \n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        # 先计算每个节点的入度\n",
    "        in_degree = [0 for _ in range(1005)]\n",
    "        for _, v in edges:\n",
    "            in_degree[v] += 1\n",
    "        # 并查集是用来判断是否是一棵树的\n",
    "        for u, v in edges[::-1]:\n",
    "            if in_degree[v] == 2:\n",
    "                # 判断移走这条边之后是否是一个树\n",
    "                if self.istree_afterremove(edges, u, v):\n",
    "                    return [u, v]\n",
    "        # 如果没有入度为2的节点，说明有环\n",
    "        return self.find_remove_edge(edges)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        father = [i for i in range(1005)]\n",
    "        def find(a):\n",
    "            if a == father[a]:\n",
    "                return a\n",
    "            else:\n",
    "                father[a] = find(father[a])\n",
    "                return father[a] \n",
    "\n",
    "        def join(a,b):\n",
    "            a = find(a)\n",
    "            b = find(b)\n",
    "            if a == b:\n",
    "                return \n",
    "            else:\n",
    "                father[a] = b\n",
    "\n",
    "        def issame(a,b):\n",
    "            a = find(a)\n",
    "            b = find(b)\n",
    "            return a == b\n",
    "\n",
    "        def entertwo(a): # 多的那个路径是指向树中的节点\n",
    "            father = [i for i in range(100)]\n",
    "            for i in range(len(edges)):\n",
    "                if edges[i][0] == a:continue\n",
    "                if issame(edges[i][0],edges[i][1]):\n",
    "                    return False # 如果屏蔽了a，其余的还是有重复，就说明应该删除另一个\n",
    "                join(edges[i][0],edges[i][1])\n",
    "            return True # 如果屏蔽了a,其余的可以组成一个树，就说明a是多余的\n",
    "\n",
    "        def outtwo(): # 多的那个路径是被树中的路径指向\n",
    "            father = [i for i in range(100)]\n",
    "            for i in range(len(edges)):\n",
    "                if issame(edges[i][0],edges[i][1]):\n",
    "                    return edges[i]\n",
    "                else:\n",
    "                    join(edges[i][0],edges[i][1])\n",
    "\n",
    "        enter = {}\n",
    "        twoD = [] # 保存的是指向的是入度为2的节点的起始节点，有两个\n",
    "        twoend = 0 # 用以保存入度为2的节点，只会有一个\n",
    "        for i in range(len(edges)):\n",
    "            enter[edges[i][1]] = enter.get(edges[i][1],0) + 1\n",
    "        for k,v in enter.items():\n",
    "            if v == 2:\n",
    "                for i,j in edges:\n",
    "                    if j == k:\n",
    "                        twoD.append(i)\n",
    "                        twoend = k\n",
    "        if twoD:#如果有入度为2的情况，则一定是有两条边，一定是删除入度为2的节点的两条边的其中一条\n",
    "            if entertwo(twoD[1]):\n",
    "                return [twoD[1],twoend]#因为要输出最后出现的答案，先处理后面的节点\n",
    "            else:\n",
    "                return [twoD[0],twoend]\n",
    "        return outtwo()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "\n",
    "        def find(i):\n",
    "            if father[i]==i:\n",
    "                return i\n",
    "            else:\n",
    "                father[i] = find(father[i])\n",
    "                return father[i]\n",
    "        def check(f,z):\n",
    "            # print(f,z)\n",
    "            father = list(range(1001)) #定义在内部\n",
    "            def find(i):\n",
    "                if father[i]==i:\n",
    "                    return i\n",
    "                else:\n",
    "                    father[i] = find(father[i])\n",
    "                    return father[i]\n",
    "            for i,j in edges :\n",
    "                if i==f and j==z:\n",
    "                    continue\n",
    "                i0 = find(i) #根\n",
    "                j0 = find(j) #子\n",
    "                print(i,j,i0,j0,father[:10])\n",
    "                if i0 == j0: #成环\n",
    "                    # print()\n",
    "                    return False\n",
    "                elif j0!=j and j0!=i:\n",
    "                    # print()\n",
    "                    return False #多根\n",
    "                else:\n",
    "                    father[j] = i0\n",
    "            return True\n",
    "\n",
    "        father_num = [0]*1001\n",
    "\n",
    "        for i,j in edges:\n",
    "            father_num[j]+=1\n",
    "        print(father_num[:10])\n",
    "        #多个根\n",
    "        duogen = []\n",
    "        for i,j in edges[::-1]:\n",
    "            if father_num[j]==2:\n",
    "                duogen.append([i,j])\n",
    "        if duogen:\n",
    "            # if father_num[duogen[0][0]]==0: #没有根的是根——错的——两种是同一个根\n",
    "            #     return duogen[1]\n",
    "            if check(duogen[0][0],duogen[0][1]):\n",
    "                return duogen[0]\n",
    "            else:\n",
    "                return duogen[1]\n",
    "\n",
    "\n",
    "        #环\n",
    "        father = list(range(1001))\n",
    "        for i,j in edges:\n",
    "            i0 = find(i) #根\n",
    "            j0 = find(j) #子\n",
    "\n",
    "            if i0 == j0:\n",
    "                return [i,j]\n",
    "            # elif j0!=j and j0!=i:\n",
    "                # return[i,j] #多爹\n",
    "            else:\n",
    "                father[j] = i0\n",
    "          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        def find(i):\n",
    "            if fa[i] == i:\n",
    "                return i\n",
    "            else:\n",
    "                fa[i] = find(fa[i])\n",
    "                return fa[i]\n",
    "        def join(i, j):\n",
    "            u = find(i)\n",
    "            v = find(j)\n",
    "            if u != v:\n",
    "                fa[v] = u\n",
    "                return None\n",
    "            if u == v:\n",
    "                return [i, j]\n",
    "        # in-degree == 2\n",
    "        import collections\n",
    "        indegree_dict = collections.defaultdict(int)\n",
    "        for i, j in edges:\n",
    "            indegree_dict[j] += 1\n",
    "        fa = [i for i in range(0, 1001)]\n",
    "        cands = []\n",
    "        result = None\n",
    "        for i, j in edges:\n",
    "            if indegree_dict[j] == 2:\n",
    "                cands.append([i,j])\n",
    "            else:\n",
    "                tmpresult = join(i, j)\n",
    "                result = tmpresult if tmpresult is not None else result\n",
    "        if not cands:\n",
    "            return result\n",
    "        else:\n",
    "            print(fa)\n",
    "            if find(cands[1][0]) == find(cands[1][1]): # must rm the second one\n",
    "                return cands[1]\n",
    "            elif find(cands[0][0]) == find(cands[0][1]): # must rm the first one\n",
    "                return cands[0]\n",
    "            else: # both will be ok\n",
    "                return cands[1]\n",
    "            \n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
